Liczba chromatyczna

[fibi]

Udowodnij, że jeśli \(\displaystyle{ G}\) jest grafem n-wierzchołkowym, to \(\displaystyle{ \chi(G) + \chi (G') \geqslant 2 \sqrt{n}}\). Podaj przykład nieskończonej rodziny grafów pokazującej, że tego oszacowania nie można wzmocnić.

[miodzio1988]

Dla dowolnych liczb rzeczywistych prawdziwa jest nierówność:
\(\displaystyle{ (a+b) ^{2} \ge 4ab}\)
Oznaczenia:
\(\displaystyle{ a= \chi (G)}\)
\(\displaystyle{ b= \chi (G')}\)
a i b to są liczb dodatnie więc pierwiastkujemy stronami
\(\displaystyle{ a+b \ge 2 \sqrt{ab} \ge(*) \ge 2 \sqrt{n}}\)
CKD
\(\displaystyle{ (*)}\)-korzystamy z nierowności :
\(\displaystyle{ \chi (G') \cdot \chi (G) \ge n}\)
jak chcesz to mogę to też udowodnić.

Drugą część zadania już zrobisz?

[fibi]

Dzięki za pomoc, ale nie wiem jak to skończyć :/ Tzn jak udowodnić tę nierówność i znaleźć rodzinę grafów.

[miodzio1988]

Żadnego pomysłu?? Może jakieś próby? Bo jak ja Ci wszystko zrobię to niczego się nie nauczysz. Porysuj sobie grafy i zobacz, które grafy pasują nam do zadania. Rysuj cykle, drogi proste, grafy pełne, Eulerowskie , spojne, niespojne itd. Taka metoda będzie bardziej skuteczna niż gotowiec.

[Qń]

\(\displaystyle{ \chi (G') \cdot \chi (G) \ge n}\)

Uznałem, że to byłoby za proste i udowadniałem wyjściową nierówność indukcyjnie.
Ale faktycznie powyższa nierówność zachodzi i to oczywiście wystarcza.

Jej dowód jest prosty - jeśli \(\displaystyle{ \chi (G) = k}\), to po pomalowaniu \(\displaystyle{ G}\) na tych \(\displaystyle{ k}\) kolorów łatwo zauważyć, że z zasady szufladkowej Dirichleta wynika, że jest przynajmniej \(\displaystyle{ \frac{n}{k}}\) wierzchołków jednego koloru. W \(\displaystyle{ G'}\) tworzą one klikę, więc do ich pomalowania potrzeba przynajmniej \(\displaystyle{ \frac{n}{k}}\) kolorów, zatem przynajmniej tyle wynosi liczba chromatyczna dopełnienia. Zatem żądany iloczyn faktycznie jest równy co najmniej \(\displaystyle{ n}\).

A równość zachodzi gdy \(\displaystyle{ G}\) składa się z \(\displaystyle{ k}\) klik, każda o \(\displaystyle{ k}\) wierzchołkach.

Q.

[miodzio1988]

Jednak indukcja. Gdybym byl na egzaminie to pewnie też bym tą drogą poszedl. W domu jednak latwiej wpasc na coś sprytnego
Fajny dowód
No ja się nie uczylem zasady szufladkowej stąd trochę inaczej bym to zrobił. Ale moje wypociny zamieszczę innym razem (edytuję pozniej post), bo dzisiaj to za bardzo padnięty jestem;]
Pozdrawiam.