Matematyka.pl

Wykaż, że dla dowolnego grafu \(\displaystyle{ G}\) zachodzi nierówność

\(\displaystyle{ X(G)+X(G^c) \le \left| V\right|+1}\)
,gdzie \(\displaystyle{ X}\) to liczba chromatyczna.

Jak to zrobić?

Indukcja. Niech \(\displaystyle{ n = |V|}\). Dla \(\displaystyle{ n=1}\) teza jest oczywista.

Niech \(\displaystyle{ G}\) będzie grafem o \(\displaystyle{ n+1}\) wierzchołkach. Niech \(\displaystyle{ v}\) będzie wierzchołkiem \(\displaystyle{ G}\). Wówczas \(\displaystyle{ H := G \setminus v}\) jest grafem o \(\displaystyle{ n}\) wierzchołkach. Niech \(\displaystyle{ k = \chi(H)}\) oraz \(\displaystyle{ l = \chi(H^c)}\) oraz ustalmy pokolorowanie grafu \(\displaystyle{ H}\) \(\displaystyle{ k}\) kolorami oraz grafu \(\displaystyle{ H^c}\) \(\displaystyle{ l}\)-kolorami. Wiemy również, że dla tego grafu zachodzi nierówność
\(\displaystyle{ k+l \leq n+1.}\)
Rozpatrz dwa przypadki - albo stopień tego wierzchołka w \(\displaystyle{ G}\) jest mniejszy od \(\displaystyle{ k}\), to...
lub wynosi przynajmniej \(\displaystyle{ k}\), i wtedy jego stopień w \(\displaystyle{ G^c}\) to co najwyżej \(\displaystyle{ n-k}\), i ...