WisFaq!

Het chromatisch getal van een graaf

Ik zou graag willen weten wat een chromatorisch getal van een graaf is. Ik heb op verschillende engelse sites al gezocht, maar kon geen duidelijk antwoord vinden.

erwin rombouts
12-10-2002

Antwoord

Definitie: Een kleuring van een graaf G = (V ; E ) is een toewijzing van kleuren aan de punten van G zo dat geen twee verbonden punten dezelfde kleur hebben. Het minimale aantal kleuren nodig om de graaf G te kleuren, wordt het chromatisch getal van G genoemd.

V staat voor vertices (enkelvoud: vertex) en slaat op de verzameling van punten of knopen.
E staat voor edges (enkelvoud: edge) en slaat op de verzameling van zijden of takken.

Zie The Four Color Theorem [http://www.mathpages.com/home/kmath266/kmath266.htm]

WvR
12-10-2002