Gallai-Hasse-Roy-Vitaver-sætningen er en slags dualitet mellem vertexfarverne på en given urettet graf og orienteringerne af dens kanter. Sætningen siger, at det mindste antal farver, der kræves for en korrekt farvning af enhver graf G , er én mere end længden af den maksimale vej i retningen af grafen G , hvor denne vejlængde er minimal [1] . Orienteringer, hvor banen med maksimal længde har minimum længde, indeholder altid mindst én acyklisk orientering [2] .
En alternativ formulering af samme sætning siger, at enhver orientering af en graf med kromatisk tal k indeholder en simpel rettet vej med k hjørner [3] . Det er muligt at pålægge betingelser, så stien starter ved et hvilket som helst toppunkt, og at det fra dette toppunkt er muligt at nå et hvilket som helst andet toppunkt på den rettede graf [4] [5] .
En todelt graf kan orienteres fra en del til en anden. Den længste vej i denne orientering har kun to hjørner. Omvendt, hvis en orientering i en graf ikke indeholder en sti med længde tre, så skal ethvert toppunkt enten være en kilde (ingen indgående buer) eller en synk (ingen udgående buer), og opdeling af hjørnerne i kilde og synker viser, at dette grafen er todelt.
I enhver orientering af en grafcyklus af ulige længde er det umuligt at give alle tilstødende kanter forskellige retninger, således at to på hinanden følgende kanter danner en bane med tre hjørner. Følgelig er det kromatiske antal ulige cyklusser tre.
For at bevise, at det kromatiske tal er større end eller lig med minimumslængden af den maksimale vej, antag, at grafen er farvet med k farver for nogle k . Herefter kan grafen orienteres acyklisk ved at nummerere farverne, og hver kant kan rettes fra farven med det nederste indeks til den højere. I denne orientering stiger farveindeksene strengt langs enhver orienteret sti, så hver sti indeholder højst et toppunkt af hver farve, og det samlede antal hjørner i stien kan ikke overstige k (antallet af farver).
For at bevise, at det kromatiske tal er mindre end eller lig med minimumslængden af en maksimal bane, antag, at grafen har en orientering, hvor der højst er k hjørner i en orienteret bane for nogle k . Grafens hjørner kan farves i k farver ved at vælge en maksimal acyklisk orienteringsundergraf og derefter farve hvert hjørne med en farve med et indeks svarende til længden af den længste vej til det givne hjørne. Med en sådan farvning er hver kant af subgrafen orienteret fra et toppunkt med et lavere indeks til et toppunkt med et højere indeks, og derfor vil farvelægningen være korrekt. For hver kant, der ikke hører til undergrafen, skal der være en rettet sti inde i undergrafen, der forbinder disse to hjørner i den modsatte retning, ellers ville kanten falde ind i undergrafen. Således er kanten orienteret fra et større tal til et mindre og krænker ikke farvens korrekthed [6] .
Beviset for denne teorem blev brugt af Yury Vladimirovich Matiyasevich som en testcase for det foreslåede bevisskema i diskret matematik [7] .
Sætningen har en naturlig fortolkning i kategorierne rettede grafer og grafhomomorfismer . Homomorfisme er en kortlægning af hjørner af en graf til hjørner af en anden graf, hvor tilstødende hjørner forbliver stødende op i billedet. Så kan en k -farvning af en urettet graf G beskrives ved en homomorfi af grafen G til den komplette graf K k . Givet en orientering i en komplet graf, bliver det en turnering , og denne orientering kan bruges til at angive en orientering i graf G . Især den farvning, som den længste vej giver, svarer til en homomorfi til en transitiv turnering (en acyklisk orienteret komplet graf), og enhver farvning kan beskrives ved en sådan homomorfi til en transitiv turnering.
Hvis vi betragter homomorfier i den anden retning, til G , ikke fra G , er en rettet graf G acyklisk og har højst k toppunkter i den længste vej, hvis og kun hvis der ikke er nogen vejhomomorfi P k + 1 til G .
Således er Gallai-Hasse-Roy-Vitaver-sætningen ækvivalent med sætningen om, at der for enhver rettet graf G eksisterer en homomorfi til en transitiv turnering med k hjørner, hvis og kun hvis der ikke er homomorfi fra en sti med ( k + 1) hjørner [2] . I det tilfælde, hvor grafen G er acyklisk, kan udsagnet betragtes som en form for Mirskys sætning , at den længste kæde i et delvist ordnet sæt er lig med det mindste antal antikæder, som sættet kan opdeles i [8 ] . Udsagnet kan generaliseres fra stier til andre rettede grafer - for ethvert polytræ P eksisterer der en dobbeltrettet graf D , således at der for enhver rettet graf G eksisterer en homomorfi fra G til D , hvis og kun hvis der ikke er isomorfi fra P til G [9] .
Gallai-Hasse-Roy-Vitaver-sætningen er gentagne gange blevet genopdaget [2] . Sætningen har fået sit navn fra separate publikationer af T. Gallai [10] , M. Hasse [11] , B. Roy [12] og L. M. Vitaver [13] . Roy tilskriver formuleringen af sætningen Claude Berge , der udtalte det som en formodning i en bog om grafteori i 1958 [12] .