Liczba chromatyczna grafu.

[Fengson]

Graf \(\displaystyle{ G=(G,E)}\) jest określony w następujący sposób : \(\displaystyle{ V = \{10,11,...,99\}, xy \in E \Leftrightarrow x}\) i \(\displaystyle{ y}\) mają tę samą cyfrę jedności, lub tę samą cyfrę dziesiątek. Wyznacz liczbę chromatyczną grafu.

Obliczyłem, że jest 765 krawędzi, stopień każdego wierzchołka to 17.
Myślałem, żeby skorzystać ze wzoru :

"Graf, którego wszystkie wierzchołki mają stopień nie większy niż k jest (k+1)-kolorowalny."

Tylko on jest chyba dla grafów pełnych? Jak wyznaczyć tę liczbę dla dowolnego grafu? Szczególnie tak dużego, jak taki?

[patry93]

Dokładniej, to to nie jest wzór, a twierdzonko (i działa dla dowolnych grafów). W każdym razie, z tego tw. otrzymujemy oszacowanie górne na liczbę chromatyczną (na pewno jest nie większa niż 18).

Błąd:    

Z drugiej strony, zauważ, że lb. chrom. możemy również oszacować z dołu przez 18 (w ogólności, patrzymy na najmniejszy stopień występujący pośród wierzchołków - widzisz, dlaczego?).
Stąd odp. to 18. (i nawet nie trzeba pokazywać przykładowego kolorowania : ))

EDIT do postu niżej:
Ajajaj, oczywiście, zagalopowałem się.

[LisuBB]

Z drugiej strony, zauważ, że lb. chrom. możemy również oszacować z dołu przez 18 (w ogólności, patrzymy na najmniejszy stopień występujący pośród wierzchołków - widzisz, dlaczego?).

Tak nie za bardzo. To, że mamy wierzchołek o stopniu 100 nie znaczy, że potrzebujemy 100 kolorów. Przykład: drzewo o korzeniu, który ma 100 dzieci - wystarczą 2 kolory, a nie 100 jak mówi to "twierdzenie".

Ogólnie wierzchołek postaci \(\displaystyle{ 10a+b}\) (czyli \(\displaystyle{ a}\)-cyfra dziesiątek, \(\displaystyle{ b}\)-cyfra jedności) kolorujemy na kolor \(\displaystyle{ (a+b) mod 10}\). I takie kolorowanie łatwo sprawdzić, że pasuje.

Z drugiej strony mamy klikę \(\displaystyle{ K_{10}}\) - wierzchołki \(\displaystyle{ 10,11,...,19}\) zatem musimy użyć co najmniej 10 kolorów.

Co do twierdzenia:

"Graf, którego wszystkie wierzchołki mają stopień nie większy niż k jest (k+1)-kolorowalny."

trzeba rozróżnić pojęcia, że graf jest k-kolorowalny i to że jego liczba chromatyczna wynosi k.
Otóż, to że graf jest k-kolorowalny to nic innego jak stwierdzenie, że przy pomocy k kolorów jesteśmy w stanie go pokolorować (wcale nie oznacza to, że musimy użyć wszystkich k kolorów).
Z kolei liczba chromatyczna grafu to najmniejsza liczba naturalna \(\displaystyle{ p}\) taka, że graf ten jest \(\displaystyle{ p}\)-kolorowalny.