Page 8 - Grafentheorie HS 3 Graafkleuringen

HS 3 Graafkleuringen

3.3.3 Lijnkleuren van grafen

Men kan in plaats van de knopen van een graaf ook de bogen (kanten of lijnen) van een graaf kleuren.
De definitie van een lijnkleuring is vergelijkbaar met die van een knopenkleuring.

Bij het kleuren van de knopen in een graaf mochten knopen die een boog gemeenschappelijk hadden
niet dezelfde kleur krijgen.

Bij lijnkleuring van een graaf mogen bogen die een knoop gemeenschappelijk hebben niet dezelfde kleur
krijgen.

Het minimaal aantal kleuren dat er nodig is om de lijnen (bogen) van een graaf te kleuren noemt men
het (lijn)kleurgetal van de graaf.
Voorbeeld: Petersengraaf

In de grafentheorie wordt de zogenaamde graaf van Petersen (Deense wiskundige) dikwijls als
voorbeeld gebruikt.

Hieronder de knopenkleuring (links) en de bogenkleuring (rechts) van de Petersengraaf.

Kleurgetal is 3 Kleurgetal is 4

https://www.geogebra.org/m/wf7qfayt en https://www.geogebra.org/m/njv2hjhr

Er bestaat geen eenvoudig algoritme voor het lijnkleuren van een graaf. t
e
n
.
Stelling 1 o
l
Het (lijn)kleurgetal van een willekeurige graaf is minstens gelijk aan de graad van de graaf. e
h
t
a
Stelling 2 m
.
König bewees in 1916 een algemene lijnkleuringsstelling voor tweedelingsgraven. w
w
Het (lijn)kleurgetal van een tweedelingsgraaf (bipartiete graaf) is gelijk aan de graad van de graaf.
w

© 2021 Ivan De Winne ivan@mathelo.net 7