WisFaq!

Graaf met chromatisch getal 5

Ik kan eigenlijk kort zijn. Ik denk dat ik het vierkleurenprobleem begrepen heb maar concludeer hieruit dat het chromatisch getal van een graaf nooit groter kan zijn dan 4. Klopt dit? Indien ik mij vergis, kan u mij dan een graaf tekenen met chromatisch getal groter dan 4?

martien achten
15-2-2006

Antwoord

Dag Martien,

Je hebt bijna gelijk: het chromatisch getal van een PLANAIRE graaf is altijd maximum 4. Een planaire graaf is een graaf die je op een blad papier kan tekenen zonder dat verschillende bogen elkaar snijden. Als je vertrekt van een wereldkaart (het oorspronkelijke vierkleurenprobleem), en je stelt elk land als top voor, en je verbindt twee toppen als de landen aan elkaar grenzen, dan krijg je zo een planaire graaf.

Maar er zijn dus ook andere (niet-planaire) grafen, en die kunnen wel een hoger chromatisch getal hebben. Het verzinnen van voorbeelden is niet zo moeilijk: denk bijvoorbeeld aan de complete graaf met vijf toppen (dus vijf toppen en alle mogelijke bogen), om die te kleuren heb je vijf kleuren nodig, dus het chromatisch getal is vijf.

Groeten,
Christophe.

Christophe
16-2-2006