Gallai-Hasse-Roy-Vitaverova věta je druh duality mezi zbarvením vrcholů daného neorientovaného grafu a orientací jeho hran. Věta říká, že minimální počet barev potřebný pro správné obarvení libovolného grafu G je o jednu větší než délka maximální cesty v orientaci grafu G , ve které je tato délka cesty minimální [1] . Orientace, ve kterých má dráha maximální délky minimální délku, obsahují vždy alespoň jednu acyklickou orientaci [2] .
Alternativní formulace stejné věty říká, že jakákoli orientace grafu s chromatickým číslem k obsahuje jednoduchou orientovanou cestu s k vrcholy [3] . Je možné klást podmínky tak, aby cesta začínala v libovolném vrcholu a aby z tohoto vrcholu bylo možné dosáhnout jakéhokoli jiného vrcholu orientovaného grafu [4] [5] .
Bipartitní graf lze orientovat z jedné části do druhé. Nejdelší cesta v této orientaci má pouze dva vrcholy. Naopak, pokud orientace v grafu neobsahuje cestu délky tři, pak jakýkoli vrchol musí být buď zdrojem (žádné příchozí oblouky) nebo jímkou (žádné odchozí oblouky), a rozdělení vrcholů na zdroj a výlevky ukazuje, že toto graf je bipartitní.
V jakékoli orientaci cyklu grafu liché délky není možné dát všem sousedním hranám různé směry, takže dvě po sobě jdoucí hrany tvoří cestu se třemi vrcholy. V souladu s tím je chromatický počet lichých cyklů tři.
Abychom dokázali, že chromatické číslo je větší nebo rovno minimální délce maximální cesty, předpokládejme, že graf je obarven k barvami pro nějaké k . Potom lze graf orientovat acyklicky očíslováním barev a každou hranu směřovat od barvy s nižším indexem k vyšší. V této orientaci se barevné indexy striktně zvyšují podél jakékoli orientované cesty, takže každá cesta obsahuje nejvýše jeden vrchol každé barvy a celkový počet vrcholů v cestě nemůže překročit k (počet barev).
Abychom dokázali, že chromatické číslo je menší nebo rovno minimální délce maximální cesty, předpokládejme, že graf má orientaci, ve které je na libovolné orientované cestě pro nějaké k nejvýše k vrcholů . Vrcholy grafu lze obarvit k barvami tak, že si vyberete podgraf s maximální acyklickou orientací a poté obarvíte každý vrchol barvou s indexem rovným délce nejdelší cesty k danému vrcholu. Při takovém zabarvení je každá hrana podgrafu orientována z vrcholu s nižším indexem do vrcholu s vyšším indexem, a proto bude vybarvení správné. Pro každou hranu, která nepatří do podgrafu, musí být uvnitř podgrafu nasměrovaná cesta spojující tyto dva vrcholy v opačném směru, jinak by hrana spadla do podgrafu. Okraj je tedy orientován z většího čísla na menší a nenarušuje správnost vybarvení [6] .
Důkaz této věty použil Yury Vladimirovich Matiyasevich jako testovací případ pro navrhované schéma důkazu v diskrétní matematice [7] .
Věta má přirozenou interpretaci v kategoriích orientovaných grafů a grafových homomorfismů . Homomorfismus je mapování vrcholů jednoho grafu na vrcholy jiného grafu, ve kterém sousední vrcholy zůstávají v obraze sousedící. Potom lze k -zabarvení neorientovaného grafu G popsat homomorfismem grafu G do úplného grafu K k . Za předpokladu orientace v úplném grafu se z něj stane turnaj , a tuto orientaci lze použít ke specifikaci orientace v grafu G . Konkrétně zbarvení dané nejdelší cestou odpovídá homomorfismu do tranzitivního turnaje (acyklicky orientovaného kompletního grafu) a jakékoliv zbarvení lze tímto homomorfismem popsat do tranzitivního turnaje.
Uvažujeme-li homomorfismy v opačném směru, do G , nikoli z G , je orientovaný graf G acyklický a má nejvýše k vrcholů na nejdelší dráze právě tehdy, když neexistuje homomorfismus cesty P k + 1 ke G .
Gallai-Hasse-Roy-Vitaverova věta je tedy ekvivalentní větě, že pro jakýkoli orientovaný graf G existuje homomorfismus do tranzitivního turnaje s k vrcholy právě tehdy, když neexistuje homomorfismus z cesty s ( k + 1) vrcholy [2] . V případě, že je graf G acyklický, lze za formu věty považovat tvrzení , že nejdelší řetězec v částečně uspořádané množině je roven minimálnímu počtu antiřetězců, na které lze množinu rozdělit [8 ] . Tvrzení lze zobecnit z cest k jiným orientovaným grafům — pro jakýkoli polytree P existuje duální orientovaný graf D takový, že pro jakýkoli orientovaný graf G existuje homomorfismus od G do D právě tehdy, když neexistuje izomorfismus z P až G [9] .
Gallai-Hasse-Roy-Vitaverova věta byla opakovaně znovuobjevena [2] . Věta získala své jméno podle samostatných publikací T. Gallaie [10] , M. Hasse [11] , B. Roye [12] a L. M. Vitavera [13] . Roy připisuje formulaci teorému Claude Berge , který ji uvedl jako domněnku v knize o teorii grafů v roce 1958 [12] .