Konstrukce Hayosh

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.

Budova

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 .

Sestrojené grafy

O grafu Gk se říká, že je sestavitelný (nebo k -konstruovatelný podle Hajoshe), pokud je vytvořen jedním ze tří způsobů [ 2] :

Odkaz na barvení

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] .

Sestrojitelnost kritických grafů

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] .

Hayoshovo číslo

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] .

Jiné aplikace

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ů .

Poznámky

  1. Hajos, 1961 .
  2. 12 Diestel , 2006 .
  3. Důkaz této skutečnosti lze nalézt také v Diestel ( Diestel 2006 ).
  4. Jensen, Toft, 1994 , str. 184.
  5. Gravier, 1996 .
  6. Kubale, 2004 .
  7. Catlin, 1979 .
  8. Jensen, Royle, 1999 .
  9. Diestel ( 2006 ) na to odkazuje, když píše, že posloupnost operací „není vždy krátká“. Jensen a Toft ( 1994 , 11.6 Délka Hajósových důkazů, s. 184–185) předložili jako otevřený problém určení minimálního počtu kroků k sestrojení libovolného n -vertexového grafu.
  10. Mansfield, Wales, 1982 .
  11. 1 2 Pitassi, Urquhart, 1995 .
  12. Iwama, Pitassi, 1995 .
  13. Koester, 1991 .
  14. Liu, Zhang, 2006 .
  15. Euler, 2003 .

Literatura