Page 13 - Grafentheorie HS 3 Graafkleuringen

HS 3 Graafkleuringen

Definitie:
Het kleurgetal van een graaf is het kleinste aantal kleuren dat nodig is om de graaf te kleuren.

Het kleurgetal van een graaf G wordt genoteerd als χ(G)
χ(G) lees je als “de Chi van G” waarbij Chi de eerste letter is van het Griekse woord “Chroma” dat kleur
betekent.
Een andere benaming voor kleurgetal is chromatisch getal.

Het kleurgetal van graaf 1 is 3.
Het kleurgetal van graaf 2 is 2.

3.6.1 Uitgewerkt voorbeeld

Kleur met de methode uit de vorige paragraaf de volgende graaf met een minimaal aantal kleuren en
bepaal het kleurgetal.
Stap 1: bepaal van elke knoop van de graaf de graad.

Stap 2: kleur de knoop met de hoogste graad en herhaal deze werkwijze voor de volgende knoop.

Stap 3: Kleur nu ook de overige knopen zodanig dat geen 2 knopen die verbonden zijn dezelfde kleur t
krijgen. e
n
.
o
l
e
h
t
a
m
.
w
w
w
Het kleurgetal van deze graaf is 3.

© 2021 Ivan De Winne ivan@mathelo.net 12