WisFaq!

Kleuringen van grafen

We hebben opgemerkt dat voor een graaf g een ondergrens voor X(G) kunnen vinden door te zoeken naar de grootste volledige deelgraaf Kn in G.
Kunnen we ook iets zeggen over een bovengrens voor X(G). Jazeker, toon aan dat bovengrens gegeven wordt met [1 + maximale valentie].

Kan iemand mij helpen met bovenstaande vraag?

Alvast bedankt!

Groeten

johan
8-12-2010

Antwoord

Laten we is uitgaan van het 'worst case scenario': de complete graaf (ook wel clique genoemd). In een clique zijn alle knopen verbonden met elkaar maar niet met zichzelf*, dus hebben alle knopen een andere kleur. Het chromatisch getal (X(G)) van een clique is dus gelijk aan het aantal knopen N. De maximale valentie ($
\Delta
$N) van een complete graaf met N knopen is N-1 (want knopen zijn niet met zichzelf verbonden).

Aangezien X(G) = N en $
\Delta
$N = N-1 is eenvoudig te zien dat X(G) = $
\Delta
$N + 1

Het is niet denkbaar dat een graaf meer kleuren nodig heeft dan knopen, dus dit is het absolute maximum voor X(G).

*=Voor een graaf waarvan de knopen ook met zichzelf zijn verbonden is het chromatisch getal niet te bepalen en ook niet informatief.

Ter (overbodige) informatie:
Volgens Brook's theorema geldt dat voor alle grafen behalve complete grafen en cyclische grafen met een oneven aantal knopen het aantal kleuren gelijk is aan de maximale valentie, dus: X(G) = $
\Delta
$N.

Coen
14-12-2010