Liczba chromatyczna i dopełnienie grafu

[gardner]

1.Jeśli \(\displaystyle{ G}\) jest grafem \(\displaystyle{ k}\)-regularnym o \(\displaystyle{ p}\) wierzchołkach to
\(\displaystyle{ X(G) \ge \frac{p}{p-k}}\)

2. Dla każdego grafu \(\displaystyle{ G}\) o \(\displaystyle{ p}\) wierzchołkach \(\displaystyle{ X(G)X'(G ) \ge p}\).

W pierwszym zadaniu próbowałem wyjść ze znanej nierówności:
\(\displaystyle{ \frac{p}{ \beta _{0}} \le X(G) \le p- \beta _{0}+1}\)

Wystarczy więc wykazać, że
\(\displaystyle{ p-k \ge \beta _{0}}\) ?

[bartek118]

Używasz jakichś nieklasycznych oznaczeń?
Rozumiem, że \(\displaystyle{ X(G) = \chi (G)}\)? Czym jest \(\displaystyle{ \beta_0}\)?

[gardner]

Tak, powinno być \(\displaystyle{ \chi}\). \(\displaystyle{ \beta _{0}}\) jest największą licznością niezależnego zbioru wierzchołków.

[bartek118]

Odnośnie 2, rozumiem, że miało być \(\displaystyle{ \chi(G) \chi (G') \geq p}\)

Niech \(\displaystyle{ V_1, V_2, \ldots}\) będzie rozbiciem \(\displaystyle{ V}\) odpowiadającym najlepszemu kolorowaniu \(\displaystyle{ G}\). Każdy z tych zbiorów jest kliką w \(\displaystyle{ G'}\), więc
\(\displaystyle{ \chi(G') \geq \max \{ |V_j| \ : j=1,\ldots, \chi(G) \} \geq \frac{p}{\chi(G)},}\)
co kończy dowód.

[gardner]

Co oznacza najlepsze kolorowanie? Że używamy jak najmniej kolorów?

[bartek118]

Tak