Matematyka.pl

Nie mam pomysłu jak pokazać, że kubiczny(3-regularny) graf hamiltonowski ma indeks chromatyczny równy 3.

Z lematu o uściskach dłoni wynika, że taki graf ma parzystą liczbę wierzchołków. W takim razie rozważmy istniejącą drogę Hamiltona i pomalujmy ją na biało-czarno (w ten sposób pierwsza i ostatnia krawędź w tej drodze będzie biała). Usuńmy to co już pomalowane. Pierwszy i ostatni wierzchołek są teraz stopnia dwa, a pozostałe stopnia jeden. Jeśli dwa wyróżnione wierzchołki są połączone (czyli jeśli istnieje cykl Hamiltona), to malujemy łączącą je krawędź na czarno, a całą resztę na czerwono. Jeśli nie są połączone, to malujemy dwie krawędzie wychodzące z pierwszego wierzchołka na czarno i czerwono, i tak samo z ostatniego wierzchołka, a resztę na czerwono. W każdym przypadku wystarczyły nam trzy kolory.

Q.

Ok, dzięki. Ale u mnie graf hamiltonowski miał cykl hamiltona, a graf półhamiltonowski miał drogę hamiltona

W takim razie jest jeszcze prościej, bo końcówka argumentu jest o połowę krótsza.

Q.