A Gallai-Hasse-Roy-Vitaver tétel egyfajta kettősség egy adott irányítatlan gráf csúcsszínezése és éleinek orientációja között . A tétel kimondja, hogy bármely G gráf megfelelő színezéséhez szükséges minimális színszám eggyel több, mint a G gráf orientációjában lévő maximális út hossza, amelyben ez az úthossz minimális [1] . Azok az irányok , amelyekben a maximális hosszúságú út minimális hosszúságú, mindig tartalmaznak legalább egy aciklikus orientációt [2] .
Ugyanennek a tételnek egy alternatív megfogalmazása azt állítja, hogy a k kromatikus számú gráf bármely orientációja tartalmaz egy egyszerű irányított utat k csúcsgal [3] . Feltételeket szabhatunk meg úgy, hogy az út bármely csúcsból induljon, és ebből a csúcsból el lehessen érni az irányított gráf bármely másik csúcsát [4] [5] .
Egy kétrészes gráf orientálható egyik részről a másikra. Ebben az orientációban a leghosszabb útnak csak két csúcsa van. Ezzel szemben, ha egy gráf orientációja nem tartalmaz három hosszúságú utat, akkor bármely csúcsnak vagy forrásnak (nincs bejövő ív), vagy nyelőnek (nincs kimenő ívnek) kell lennie, és a csúcsok forrásokra és süllyesztőkre való felosztása azt mutatja, hogy ez a gráf kétoldalú.
Egy páratlan hosszúságú gráfciklus bármely orientációjában lehetetlen minden szomszédos élnek különböző irányt adni, így két egymást követő él három csúcsú utat alkot. Ennek megfelelően a páratlan ciklusok kromatikus száma három.
Annak bizonyítására, hogy a kromatikus szám nagyobb vagy egyenlő a maximális út minimális hosszával, tegyük fel, hogy a gráf k színnel van kiszínezve valamilyen k esetén . Ekkor a színek számozásával aciklikusan orientálható a gráf, és minden él az alacsonyabb indexű színtől a magasabb felé irányítható. Ebben az orientációban a színindexek szigorúan nőnek bármely orientált útvonal mentén, így minden út legfeljebb egy csúcsot tartalmazhat minden színből, és az útvonal csúcsainak teljes száma nem haladhatja meg a k -t (a színek számát).
Annak bizonyítására, hogy a kromatikus szám kisebb vagy egyenlő egy maximális út minimális hosszával, tegyük fel, hogy a gráfnak olyan orientációja van, amelyben legfeljebb k csúcs található bármely k orientált útvonalában . A gráf csúcsait k színben lehet kiszínezni, ha kiválasztunk egy maximális aciklikus orientációs részgráfot, majd minden csúcsot színezünk egy színnel, amelynek indexe megegyezik az adott csúcshoz vezető leghosszabb út hosszával. Ilyen színezéssel az algráf minden éle egy alacsonyabb indexű csúcsról egy magasabb indexű csúcsra orientálódik, így a színezés helyes lesz. Minden olyan élhez, amely nem tartozik a részgráfhoz, a részgráfon belül kell lennie egy irányított útnak, amely ezt a két csúcsot ellentétes irányban összeköti, különben az él a részgráfba esne. Így az él nagyobb számról kisebbre orientálódik, és nem sérti a színezés helyességét [6] .
Ennek a tételnek a bizonyítását Jurij Vlagyimirovics Matiyasevics használta a javasolt bizonyítási séma tesztpéldájaként a diszkrét matematikában [7] .
A tételnek természetes értelmezése van az irányított gráfok és gráfhomomorfizmusok kategóriáiban . A homomorfizmus egy gráf csúcsainak egy másik gráf csúcsaira való leképezése, amelyben a szomszédos csúcsok szomszédosak maradnak a képen. Ekkor egy irányítatlan G gráf k színezése leírható a G gráf homomorfizmusával a K k teljes gráfba . Ha egy teljes grafikonon egy tájolást adunk, abból verseny lesz , és ez az orientáció használható a G grafikon orientációjának meghatározására . A leghosszabb út hosszával adott színezés egy tranzitív tornává való homomorfizmusnak felel meg (egy aciklikusan orientált teljes gráf), és bármilyen színezés leírható ezzel a homomorfizmussal tranzitív tornává.
Ha a másik irányban, G felé homomorfizmusokat tekintünk , nem G -ből, akkor egy G irányított gráf aciklikus, és legfeljebb k csúcsa van a leghosszabb úton , akkor és csak akkor, ha nincs P k + 1 G - hez való homomorfizmus .
Így a Gallai-Hasse-Roy-Vitaver tétel ekvivalens azzal a tétellel, hogy bármely irányított G gráfra akkor és csak akkor van homomorfizmus egy k csúcsú tranzitív tornává, ha nincs homomorfizmus a ( k + 1) útvonalból. csúcsok [2] . Abban az esetben, ha a G gráf aciklikus, a Mirsky-tétel egyik formájának tekinthető az az állítás, hogy egy részlegesen rendezett halmazban a leghosszabb lánc egyenlő azoknak az antiláncoknak a minimális számával, amelyekbe a halmaz felosztható [8 ] . Az állítás általánosítható útvonalakból más irányított gráfokhoz – bármely P polifához létezik egy duálisan irányított D gráf , így bármely irányított G gráfhoz akkor és csak akkor létezik homomorfizmus G -ből D -be , ha nincs izomorfizmus P -től G -ig [9] .
A Gallai-Hasse-Roy-Vitaver tételt többször is újra felfedezték [2] . A tétel nevét T. Gallai [10] , M. Hasse [11] , B. Roy [12] és L. M. Vitaver [13] külön publikációiról kapta . Roy a tétel megfogalmazását Claude Berge -nek tulajdonítja , aki egy 1958-as gráfelméleti könyvben [12] sejtésként állította azt .