Matematyka.pl

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?

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.

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.

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

librusss pisze: 8 gru 2020, o 14:45 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 }}\) ?

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

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

mol_ksiazkowy pisze: 9 gru 2020, o 09:14
A co gdy graf jest dwudzielny \(\displaystyle{ K_{n,n }}\) ?

Zgrabny kontrprzykład.

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

?