Kolorowanie grafów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
dusia17
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 4 lis 2007, o 20:59
Płeć: Kobieta
Lokalizacja: rrr
Podziękował: 2 razy

Kolorowanie grafów

Post autor: dusia17 »

Hej! Mam problem z kilkoma zadaniami dotyczącymi grafów... Oto one:

1. Niech \(\displaystyle{ G}\) będzie grafem. Pokazać, że ma on co najmniej \(\displaystyle{ \chi (G)}\) wierzchołków stopnia \(\displaystyle{ \chi (G)-1}\) lub większego.
2. Niech \(\displaystyle{ G}\) będzie grafem o \(\displaystyle{ n}\) wierzchołkach i niech \(\displaystyle{ G'}\)będzie jego dopełnieniem. Pokazać, że \(\displaystyle{ \chi (G) \chi (G') q n}\) oraz \(\displaystyle{ \chi (G) + \chi (G') q n+1.}\)
3. Udowodnić, że jeśli \(\displaystyle{ G}\) jest grafem planarnym, który nie zawiera trójkątów, to jest 4-barwny.

Wielkie dzięki za wszelką pomoc.
ODPOWIEDZ