Teorema Gallai-Hasse-Roy-Vitaver este un fel de dualitate între colorațiile vârfurilor unui graf nedirecționat dat și orientările muchiilor acestuia. Teorema afirmă că numărul minim de culori necesare pentru o colorare corectă a oricărui grafic G este cu unul mai mult decât lungimea traseului maxim în orientarea graficului G , în care această lungime a căii este minimă [1] . Orientările în care traseul de lungime maximă are lungime minimă conțin întotdeauna cel puțin o orientare aciclică [2] .
O formulare alternativă a aceleiași teoreme afirmă că orice orientare a unui graf cu număr cromatic k conține un drum simplu direcționat cu k vârfuri [3] . Este posibil să se impună condiții astfel încât calea să înceapă de la orice vârf, iar de la acest vârf să se ajungă la orice alt vârf al graficului direcționat [4] [5] .
Un graf bipartit poate fi orientat de la o parte la alta. Cea mai lungă cale în această orientare are doar două vârfuri. Dimpotrivă, dacă o orientare într-un grafic nu conține o cale de lungimea de trei, atunci orice vârf trebuie să fie fie o sursă (fără arce de intrare) fie o chiuvetă (fără arce de ieșire), iar împărțirea vârfurilor în sursă și chiuvetă arată că acest lucru graficul este bipartit.
În orice orientare a unui ciclu grafic de lungime impară, este imposibil să se dea tuturor muchiilor adiacente direcții diferite, astfel încât două muchii consecutive să formeze o cale cu trei vârfuri. În consecință, numărul cromatic al ciclurilor impare este trei.
Pentru a demonstra că numărul cromatic este mai mare sau egal cu lungimea minimă a căii maxime, să presupunem că graficul este colorat cu k culori pentru unele k . Apoi graficul poate fi orientat aciclic prin numerotarea culorilor, iar fiecare muchie poate fi direcționată de la culoarea cu indicele inferior către cea mai mare. În această orientare, indicii de culoare cresc strict de-a lungul oricărei căi orientate, astfel încât fiecare cale să conțină cel mult un vârf din fiecare culoare, iar numărul total de vârfuri din cale să nu depășească k (numărul de culori).
Pentru a demonstra că numărul cromatic este mai mic sau egal cu lungimea minimă a unui drum maxim, să presupunem că graficul are o orientare în care există cel mult k vârfuri în orice cale orientată pentru unele k . Vârfurile graficului pot fi colorate în k culori prin alegerea unui subgraf de orientare aciclică maximă și apoi colorând fiecare vârf cu o culoare cu un indice egal cu lungimea drumului cel mai lung către vârful dat. Cu o astfel de colorare, fiecare margine a subgrafului este orientată de la un vârf cu un indice mai mic la un vârf cu un indice mai mare și, prin urmare, colorarea va fi corectă. Pentru fiecare muchie care nu aparține subgrafului, trebuie să existe o cale direcționată în interiorul subgrafului care conectează aceste două vârfuri în direcția opusă, altfel muchia ar cădea în subgraf. Astfel, marginea este orientată de la un număr mai mare la unul mai mic și nu încalcă corectitudinea colorării [6] .
Dovada acestei teoreme a fost folosită de Iuri Vladimirovici Matiyasevich ca caz de testare pentru schema de demonstrare propusă în matematică discretă [7] .
Teorema are o interpretare firească în categoriile de grafuri direcționate și homomorfisme de graf . Omomorfismul este o mapare a vârfurilor unui grafic la vârfurile altui grafic, în care vârfurile adiacente rămân adiacente în imagine. Atunci o k -colorare a unui grafic nedirecționat G poate fi descrisă printr-un homomorfism al graficului G în graficul complet K k . Având în vedere o orientare într-un grafic complet, acesta devine un turneu , iar această orientare poate fi folosită pentru a specifica o orientare în graficul G. În special, colorarea dată de calea cea mai lungă corespunde unui homomorfism într-un turneu tranzitiv (un grafic complet orientat aciclic), iar orice colorare poate fi descrisă printr-un astfel de homomorfism într-un turneu tranzitiv.
Dacă luăm în considerare homomorfisme în cealaltă direcție, către G , nu din G , un graf direcționat G este aciclic și are cel mult k vârfuri pe calea cea mai lungă dacă și numai dacă nu există homomorfism de cale P k + 1 către G .
Astfel, teorema Gallai-Hasse-Roy-Vitaver este echivalentă cu teorema că pentru orice graf direcționat G există un homomorfism într-un turneu tranzitiv cu k vârfuri dacă și numai dacă nu există homomorfism dintr-o cale cu ( k + 1) vârfuri [2] . În cazul în care graficul G este aciclic, afirmația poate fi considerată ca o formă a teoremei lui Mirsky că cel mai lung lanț dintr-o mulțime parțial ordonată este egal cu numărul minim de antilanțuri în care mulțimea poate fi împărțită [8] ] . Declarația poate fi generalizată de la căi către alte grafuri direcționate — pentru orice arbore polivalent P există un graf dublu direcționat D astfel încât pentru orice graf direcționat G există un homomorfism de la G la D dacă și numai dacă nu există izomorfism din P la G [9] .
Teorema Gallai-Hasse-Roy-Vitaver a fost redescoperită în mod repetat [2] . Teorema și-a primit numele din publicații separate ale lui T. Gallai [10] , M. Hasse [11] , B. Roy [12] și L. M. Vitaver [13] . Roy îi atribuie formularea teoremei lui Claude Berge , care a afirmat-o ca o presupunere într-o carte despre teoria grafurilor în 1958 [12] .