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.
Liczba chromatyczna a antyklika w grafie
-
- 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
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) .}\)
-
- Użytkownik
- Posty: 6
- Rejestracja: 30 lis 2013, o 21:09
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz