Suma liczb chromatycznych dowolnego grafu i jego dopełnienia

[librusss]

W jaki sposób można udowodnić (lub pokazać, że to nie zachodzi), że $$\chi(G) + \chi(\overline{G}) \geq n$$gdzie G to dowolny graf o n-wierzchołkach?

[kerajs]

Może tak:
Wybieram dowolny wierzchołek. Jest on stopnia \(\displaystyle{ k }\), gdzie \(\displaystyle{ k \in \left\{ 0,1,..., n-1\right\} }\) więc liczba barw potrzebna do pokolorowania tego wierzchołka i wierzchołków z którymi jest połączony wynosi \(\displaystyle{ k+1}\), a stąd \(\displaystyle{ \chi(G) \ge k+1}\) .
W grafie dopełniającym ten sam wierzchołek jest stopnia \(\displaystyle{ n-1-k}\), więc \(\displaystyle{ \chi(\overline{G}) \ge n-1-k+1}\) .
Wychodzi ciut mocniejsza teza:\(\displaystyle{ \chi(G) + \chi(\overline{G}) \ge n+1 }\)
Jest tak dlatego, iż założyłem że graf ma więcej niż jeden wierzchołek (wybrany wierzchołek ma sąsiadów z którymi jest lub nie jest połączony), i dla takich grafów będzie ona prawdziwa.

Dołóż przypadek \(\displaystyle{ n=1}\) a otrzymasz tezę z zadania.

[mol_ksiazkowy]

Wybieram dowolny wierzchołek. Jest on stopnia \(\displaystyle{ k }\), gdzie \(\displaystyle{ k \in \left\{ 0,1,..., n-1\right\} }\) więc liczba barw potrzebna do pokolorowania tego wierzchołka i wierzchołków z którymi jest połączony wynosi \(\displaystyle{ k+1}\), a stąd \(\displaystyle{ \chi(G) \ge k+1}\) .

No ale np. drzewa są \(\displaystyle{ 2 }\) chromatyczne, a mogą mieć wierzchołki większych stopni...itd.

[kerajs]

O, bardzo dziękuję za czujność. Jakieś totalne bzdury tam powypisywałem. Przepraszam.

[mol_ksiazkowy]

W jaki sposób można udowodnić (lub pokazać, że to nie zachodzi), że $$\chi(G) + \chi(\overline{G}) \geq n$$gdzie G to dowolny graf o n-wierzchołkach?

A co gdy graf jest dwudzielny \(\displaystyle{ K_{n,n }}\) ?

[arek1357]

Tu jest prosty dowód niby czegoś prawie odwrotnego:

Grafy-liczba chromatyczna, dopełnienia i dwudzielność

[kerajs]

A co gdy graf jest dwudzielny \(\displaystyle{ K_{n,n }}\) ?

Zgrabny kontrprzykład.

[mol_ksiazkowy]

$$\chi(G) \chi(\overline{G}) \geq n$$

?

Ukryta treść:    

Istnieje choć jedna krawędź między dowolnymi kolorami tj. \(\displaystyle{ k = E(G) \geq {\chi(G) \choose 2} }\)itd.