Liczba chromatyczna, a najdłuższa ścieżka w grafie

[ucaps]

Witam.
Próbuję uporać się z następującym zadaniem:

Wykaż, że dla \(\displaystyle{ k}\) będącego długością najdłuższej ścieżki w grafie, zachodzi: \(\displaystyle{ x \le k+1}\), gdzie \(\displaystyle{ x}\) to liczba chromatyczna grafu.

Jakieś wskazówki?
Pozdrawiam.

[bartek118]

To nie jest prawdą. Rozważ dowolny cykl \(\displaystyle{ C_n}\), dla \(\displaystyle{ n \geq 4}\). Liczba chromatyczna \(\displaystyle{ x=2}\) lub \(\displaystyle{ x=3}\) (w zależności od \(\displaystyle{ n}\)), zaś \(\displaystyle{ k = n}\).

[ucaps]

Przepraszam, odwrotnie zapisałem nierówność. Już poprawione.

[bartek118]

Ustalmy wierzchołek \(\displaystyle{ v}\) w \(\displaystyle{ G}\). Rozważ drzewo rozpinające ten graf wygenerowane przez DFS-a o korzeniu w \(\displaystyle{ v}\). Wtedy wysokość tego drzewa to co najwyżej \(\displaystyle{ k}\). Z konstrukcji drzewa wynika, że wierzchołki na głębokości \(\displaystyle{ d}\) w tym drzewie nie są połączone krawędziami. Możemy je zatem pokolorować tym samym kolorem. Zatem na głębokości \(\displaystyle{ 1}\) malujemy kolorem \(\displaystyle{ c_1}\), na głębokości \(\displaystyle{ 2}\) kolorem \(\displaystyle{ c_2}\), ...., na głębokości \(\displaystyle{ k}\) kolorem \(\displaystyle{ c_k}\). Na koniec wierzchołek \(\displaystyle{ v}\) malujemy kolorem \(\displaystyle{ c_{k+1}}\). Mamy zatem pokolorowanie \(\displaystyle{ k+1}\) kolorami, więc
\(\displaystyle{ \chi(G) \leq k+1.}\)

[Mruczek]

W rozw. zad. 6 stąd: jest też inne rozwiązanie.

Btw. te zadanka z kursu teorii grafów są fajne: .

Jeszcze inaczej: indukcja w silnym sensie po długości najdłuższej ścieżki w grafie.
Pierwszy krok: długość najdłuższej ścieżki to \(\displaystyle{ 0}\). Wtedy graf to zbiór niezależny, można pokolorować go jednym kolorem.
Krok indukcyjny: Zał, że długość najdłuższej ścieżki w grafie to \(\displaystyle{ l}\). Znajdujemy w grafie maksymalny zbiór niezależny \(\displaystyle{ X}\). Kolorujemy go jednym kolorem i usuwamy go z grafu, trzeba pokazać, że pozostały graf da się pokolorować \(\displaystyle{ l}\) kolorami. Pokażemy, że w pozostałym grafie długość najdłuższej ścieżki to \(\displaystyle{ l - 1}\), wtedy z założenia indukcyjnego będzie można go pokolorować \(\displaystyle{ l}\) kolorami.
Przypuśćmy nie wprost, że w pozostałym grafie istnieje ścieżka długości \(\displaystyle{ l}\). Skoro w \(\displaystyle{ X}\) nie było żadnego wierzchołka z tej ścieżki to znaczy, że każdy wierzchołek tej ścieżki sąsiaduje z jakimś wierzchołkiem z \(\displaystyle{ X}\), w szczególności wierzchołek na końcu tej ścieżki sąsiaduje z wierzchołkiem \(\displaystyle{ v \in X}\). Przedłużamy tą ścieżkę o wierzchołek \(\displaystyle{ v}\), dostając ścieżkę długości \(\displaystyle{ l + 1}\), ale z założenia długość najdłuższej ścieżki w tym grafie nie przekraczała \(\displaystyle{ l}\), sprzeczność.