kleuringsstrategie

Voor een graaf met weinig punten en lijnen is het vrij eenvoudig om met de hand na te gaan wat het chromatische getal is.

Voor grotere grafen kan dit een ondoenlijke opdracht worden. Er zijn vandaag de dag nog steeds geen snelle methode die voor elke willekeurige graaf G het chromatische getal X(G) geeft.

Er zijn dan toch een aantal manieren bedacht we gaan er hier twee zien.

Bij de volgende methode maken we gebruik van het begrip graad van een punt.

Voor volgende figuur geldt dan:

opdracht 6

Bepaal voor de graaf G uit figuur 11 de graad van alle punten, en bepaal daarna de kleinste graad en de grootste graad. Bepaal ook X(G).

Figuur 11: De graaf G uit opdracht 6