Hajosova konstrukce je grafová operace pojmenovaná po maďarském matematikovi György Hajose [1] , kterou lze použít ke konstrukci libovolného kritického grafu nebo jakéhokoli grafu, jehož chromatické číslo je alespoň nějaká daná prahová hodnota.
Nechť G a H jsou dva neorientované grafy , vw hrana v G a xy hrana v H. Potom Hayoshova konstrukce vytvoří nový graf, který kombinuje dva grafy spojením vrcholů v a x do jednoho vrcholu, odstraněním hran vw a xy a přidáním nové hrany wy .
Nechť G a H jsou například dva úplné grafy K 4 se čtyřmi vrcholy. Vzhledem k symetrii těchto grafů není výběr hran v těchto grafech podstatný. V tomto případě bude výsledkem aplikace Hajoshovy konstrukce Moserovo vřeteno , sedmivrcholový jednotkový graf vzdálenosti vyžadující k vybarvení čtyři barvy.
Jiný příklad, jestliže G a H jsou dva cykly délky p a q , v tomto pořadí, pak výsledkem aplikace Hyos konstrukce bude opět cyklus délky p + q − 1 .
O grafu Gk se říká, že je sestavitelný (nebo k -konstruovatelný podle Hajoshe), pokud je vytvořen jedním ze tří způsobů [ 2] :
Stačí jednoduše ukázat, že jakýkoli k -konstruovatelný graf vyžaduje alespoň k barev, aby graf správně vybarvil. U kompletního grafu K k je to skutečně zcela jasné a výsledek spojení dvou nesousedících vrcholů je nutí být obarveny stejnou barvou v libovolném vybarvení, čímž se počet barev nesnižuje. V samotné konstrukci Hajosh nová hrana wy způsobí, že alespoň jeden ze dvou vrcholů w a y bude mít barvu odlišnou od barvy vrcholu získaného spojením vrcholů v a x , takže jakékoli správné vybarvení kombinovaný graf má za následek správné obarvení jednoho ze dvou menších grafů, ze kterých byl graf získán, z čehož opět získáme potřebu k barev [2] .
Haios dokázal přesnější tvrzení, že graf vyžaduje alespoň k barev v jakémkoli správném zbarvení právě tehdy, pokud obsahuje k -konstruovatelný graf jako podgraf. Ekvivalentně každý k - kritický graf ( graf vyžadující k barev, ale každý správný podgraf vyžadující méně barev) je k - konstruovatelný [3] . Alternativně lze jakýkoli graf vyžadující k barev vytvořit kombinací Hayoshovy konstrukce, operací sjednocení dvou nesousedních vrcholů a operací přidání vrcholů nebo hran k danému grafu, počínaje úplným grafem K k [4] .
Obdobnou konstrukci lze použít pro předepsané zbarvení místo obvyklého zbarvení [5] [6] .
Pro k =3 lze jakýkoli k -kritický graf (tj. libovolný lichý cyklus) sestrojit jako k -konstruovatelný graf tak, že všechny grafy vzniklé při jeho konstrukci jsou také k -kritické. Pro k =8 to není pravda – graf, který Catlin [7] našel jako protipříklad k Hadwigerově domněnce, že k - chromatický graf je kontrahovatelný na úplný graf K k , je protipříkladem tohoto problému. Následně byly k -kritické, ale ne k -konstruovatelné grafy nalezeny pouze výhradně prostřednictvím k -kritických grafů, pro všechna k ≥ 4 . Pro k =4 je jeden takový příklad získán z grafu dvanáctistěn přidáním nové hrany ke každému páru protilehlých vrcholů [8] .
Vzhledem k tomu, že spojení dvou nesousedních vrcholů snižuje počet vrcholů ve výsledném grafu, počet operací potřebných k reprezentaci daného grafu G pomocí operací definovaných Hyoszem nemůže překročit počet vrcholů v G [9] .
Mansfield a Welsh [10] definují Hajoshovo číslo h ( G ) k - chromatického grafu G jako minimální počet kroků potřebných k sestrojení G z K k , kde při každém kroku vznikne nový graf spojením dvou dříve vytvořených grafů. , kombinování dvou nesousedních vrcholů vytvořeného před grafem nebo přidání hrany k dříve vytvořenému grafu. Ukázali, že pro graf G s n vrcholy a m hranami platí h ( G ) ≤ 2 n 2 /3 − m + 1 − 1 . Pokud má jakýkoli graf polynomické Hayoshovo číslo, je možné dokázat neobarvitelnost v nedeterministickém polynomiálním čase , a proto z toho plyne, že NP = co-NP , což je teoretiky složitosti algoritmů považováno za nepravděpodobné [11] . Není však známo, jak dokázat nepolynomiální dolní odhady pro Hajosova čísla bez určitých předpokladů o teoretické složitosti, a pokud jsou takové hranice prokázány, existence nepolynomických hranic pro některé typy Fregeho systémů v matematickém logika [11] bude okamžitě následovat .
Minimální velikost stromu výrazů popisujícího Hyos konstrukci pro daný graf G může být podstatně větší než Hyos číslo grafu G , protože nejmenší výraz pro G může opakovaně použít stejné grafy vícekrát (úspory nejsou povoleny v strom výrazů). Existují 3-chromatické grafy, pro které má nejmenší takový výrazový strom exponenciální velikost [12] .
Köster [13] použil Hajosovu konstrukci k získání nekonečné sady 4-kritických polyedrických grafů , z nichž každý má dvakrát více hran než vrcholy. Podobně Liu a Zhang [14] použili konstrukci začínající Grötschovým grafem k získání mnoha 4-kritických grafů bez trojúhelníků , o kterých ukázali, že je obtížné najít zabarvení pomocí tradičních algoritmů zpětného sledování .
V kombinatorice mnohostěnů použil Reinhard Euler [15] konstrukci Hajos ke generování faset stabilní množiny polytopů .