Hajos-konstruktion er en grafoperation opkaldt efter den ungarske matematiker György Hajos [1] , som kan bruges til at konstruere enhver kritisk graf eller enhver graf, hvis kromatiske tal er mindst en given tærskel.
Lad G og H være to urettede grafer , vw en kant i G , og xy en kant i H. Derefter danner konstruktionen af Hayosh en ny graf, der kombinerer to grafer ved at kombinere hjørnerne v og x til et toppunkt, fjerne kanterne vw og xy og tilføje en ny kant wy .
Lad for eksempel G og H være to komplette K 4 -grafer med fire hjørner. I lyset af symmetrien af disse grafer er valget af kanter i disse grafer ikke afgørende. I dette tilfælde vil resultatet af anvendelsen af Hajoshs konstruktion være Moser-spindelen , en afstandsgraf med syv hjørner, der kræver fire farver for at farve.
Et andet eksempel, hvis G og H er to cyklusser med henholdsvis længden p og q , så vil resultatet af at anvende Hyos-konstruktionen igen være en cyklus med længden p + q − 1 .
En graf G k siges at være konstruerbar (eller k -konstruerbar ifølge Hajosh), hvis den er dannet på en af tre måder [2] :
Det er tilstrækkeligt blot at vise, at enhver k -konstruerbar graf kræver mindst k farver for at farve grafen korrekt . Dette er faktisk ret klart for den komplette graf K k , og resultatet af at forbinde to ikke-tilstødende hjørner tvinger dem til at blive farvet i samme farve i enhver farve, hvilket ikke reducerer antallet af farver. I selve Hajosh-konstruktionen bevirker den nye kant wy , at mindst en af de to toppunkter w og y har en farve, der er forskellig fra farven på toppunktet opnået ved foreningen af toppunkterne v og x , således at enhver korrekt farvning af kombineret graf resulterer i en korrekt farvelægning af en af de to mindre grafer, hvorfra grafen er hentet, hvorfra vi igen får behovet for k farver [2] .
Haios beviste en mere stringent påstand om, at en graf kræver mindst k farver i enhver passende farve, hvis og kun hvis den indeholder en k -konstruerbar graf som en undergraf. Tilsvarende er enhver k -kritisk graf ( en graf, der kræver k farver, men enhver korrekt undergraf, der kræver færre farver) k -konstruerbar [3] . Alternativt kan enhver graf, der kræver k farver, dannes ved at kombinere Hayosh-konstruktionen, foreningsoperationerne af to ikke-tilstødende hjørner og operationerne med at tilføje spidser eller kanter til en given graf, begyndende med en komplet graf K k [4] .
En lignende konstruktion kan anvendes til den foreskrevne farve i stedet for den sædvanlige farve [5] [6] .
For k =3 kan enhver k -kritisk graf (det vil sige enhver ulige cyklus) konstrueres som en k -konstruerbar graf på en sådan måde, at alle graferne dannet under dens konstruktion også er k -kritiske. For k =8 er dette ikke sandt - grafen, som Catlin [7] fandt som et modeksempel til Hadwigers formodning om, at en k - kromatisk graf er sammentrækbar til en komplet graf K k er et modeksempel på dette problem. Efterfølgende blev k -kritiske, men ikke k -konstruerbare grafer kun fundet gennem k -kritiske grafer, for alle k ≥ 4 . For k =4 fås et sådant eksempel fra dodekaedergrafen ved at tilføje en ny kant til hvert par antipodale hjørner [8] .
Da foreningen af to ikke-tilstødende toppunkter reducerer antallet af toppunkter i den resulterende graf, kan antallet af operationer, der kræves for at repræsentere en given graf G ved hjælp af operationerne defineret af Hyosz, ikke overstige antallet af toppunkter i G [9] .
Mansfield og Welsh [10] definerer Hajosh-tallet h ( G ) af en k -kromatisk graf G som det mindste antal trin, der kræves for at konstruere G ud fra K k , hvor der ved hvert trin dannes en ny graf ved at kombinere to tidligere dannede grafer , ved at kombinere to ikke-tilstødende hjørner af det dannede før en graf eller tilføje en kant til en tidligere dannet graf. De viste, at for en graf G med n toppunkter og m kanter , h ( G ) ≤ 2 n 2 /3 − m + 1 − 1 . Hvis en graf har et polynomielt Hayosh-tal, følger det, at det er muligt at bevise ufarvelighed i ikke-deterministisk polynomisk tid , og derfor følger det, at NP = co-NP , hvilket anses for usandsynligt af algoritmekompleksitetsteoretikere [11] . Det vides dog ikke, hvordan man kan bevise ikke-polynomielle nedre grænser for Hajos-tallene uden nogle antagelser om teoretisk kompleksitet, og hvis sådanne grænser bevises, eksistensen af ikke-polynomielle grænser for nogle typer Frege-systemer i matematiske logik [11] vil straks følge .
Minimumsstørrelsen af et udtrykstræ , der beskriver Hyos-konstruktionen for en given graf G kan være væsentligt større end Hyos-tallet for graf G , fordi det mindste udtryk for G kan genbruge de samme grafer flere gange (besparelser er ikke tilladt i et udtrykstræ). Der er 3-kromatiske grafer, hvor det mindste udtrykstræ har eksponentiel størrelse [12] .
Köster [13] brugte Hajos-konstruktionen til at opnå et uendeligt sæt af 4-kritiske polyedriske grafer , hver med dobbelt så mange kanter som hjørner. Ligeledes brugte Liu og Zhang [14] en konstruktion, der startede med Grötsch-grafen til at opnå mange 4-kritiske trekantfrie grafer , som de viste, er svære at finde farvelægninger med traditionelle backtracking -algoritmer .
I kombinatorik af polyedre brugte Reinhard Euler [15] Hajos-konstruktionen til at generere facetter af et stabilt polytopsæt .