Mam problem z udowodnieniem nierówności:
\(\displaystyle{ \chi ' (G) + \chi' (\bar{G})}\) \(\displaystyle{ \le}\) \(\displaystyle{ 2n-2}\)
Proszę o pomoc, myślę, że trzeba to ogarniać indukcją, ale nie wiem jak uargumentować to.
Dowód z kolorowaniem.
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Dowód z kolorowaniem.
Masz to tutaj na stronie 182 (20 w PDFie):
Kod: Zaznacz cały
http://compalg.inf.elte.hu/~tony/Oktatas/TDK/FINAL/Chap%207.PDF