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ć?
Wykaż, że dla dowolnego grafu
-
- Użytkownik
- Posty: 5974
- Rejestracja: 28 lut 2010, o 19:45
- Płeć: Mężczyzna
- Lokalizacja: Toruń
- Podziękował: 15 razy
- Pomógł: 1251 razy
Re: Wykaż, że dla dowolnego grafu
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 ...
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 ...