Liczba chromatyczna a antyklika w grafie

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
MateuszGRT
Użytkownik
Użytkownik
Posty: 6
Rejestracja: 30 lis 2013, o 21:09
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz

Liczba chromatyczna a antyklika w grafie

Post autor: MateuszGRT »

Niech \(\displaystyle{ G=(V,E)}\) będzie grafem prostym a \(\displaystyle{ \alpha}\) - licznością maksymalnej antykliki w tym grafie. Wykazać, że \(\displaystyle{ \chi(G) \ge |V| / \alpha}\)

Czy ktoś mógłby mi pomóc z tym zadaniem?
Z góry dzięki
Pozdrawiam.
kicaj

Liczba chromatyczna a antyklika w grafie

Post autor: kicaj »

Wierzchołki grafu \(\displaystyle{ G}\) możemy podzielić na rozłączne klasy wierzchołków (pokolorowanych tym samym kolorem) \(\displaystyle{ V_1 , V_2 , ..., V_{\chi (G)} .}\) Ponieważ, każda taka klasa tworzy antyklikę, więc jej moc nie przekracza liczby \(\displaystyle{ \alpha}\) zatem
\(\displaystyle{ |V| =|V_1 | +...+|V_{\chi (G)} |\leqslant \sum_{j=1}^{\chi (G) } \alpha =\alpha \chi (G) .}\)
MateuszGRT
Użytkownik
Użytkownik
Posty: 6
Rejestracja: 30 lis 2013, o 21:09
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 1 raz

Liczba chromatyczna a antyklika w grafie

Post autor: MateuszGRT »

Dziękuję za pomoc
ODPOWIEDZ