Odpre glavni meni

Hedetniemijeva domneva

ovržena domneva v teoriji grafov
Zgled Hedetniemijeve domneve: tenzorski produkt cikličnih grafov in (na levi) tvori graf, ki vsebuje cikel z dolžino 15 (na desni) – nastali graf za barvanje po točkah potrebuje 3 barve.

Hedetniemijeva domneva je v teoriji grafov domneva, ki jo je formuliral Stephen Travis Hedetniemi leta 1966. Obravnava povezavo med barvanjem grafov po točkah in tenzorskim produktom grafov. Domneva pravi, da velja:

kjer χ(G) označuje kromatično število neusmerjenega končnega grafa G.

Neenakost χ(G × H) ≤ min {χ(G), χ(H)} je enostavno razumljiva – če je graf G k-pobarvan, se lahko produkt G × H k-pobarva z enakim barvanjem za vsako kopijo G v produktu, ter simetrično, če je H k-pobarvan. Tako Hedetniemijeva domneva pomeni, da se tenzorskih produktov ne da pobarvati z nepričakovano majhnim številom barv.

Protiprimer domneve je odkril Jaroslav Nikolajevič Šitov leta 2019 in tako v splošnem ovrgel domnevo.[1][2] Dokaz Šitova je zgoščen in napisan na treh straneh.[3]

Znani primeriUredi

Vsak graf z neprazno množico povezav zahteva vsaj dve barvi: če grafa G in H nista 1-pobarvljiva, oziroma, da, če vsebujeta povezavo, tudi njun produkt vsebuje povezavo in prav tako ni 1-pobarvljiv. Še posebej domneva velja, če sta grafa G ali H dvodelna, saj je njuno kromatično število enako 1 ali 2.

Podobno, če dva grafa G in H nista 2-pobarvljiva, oziroma nista dvodelna, potem oba vsebujeta cikel s sodo dolžino. Ker produkt dveh sodih cikličnih grafov vsebuje sodi cikel, prav tako tudi produkt G × H ni 2-pobarvljiv. Z drugimi besedami, če je produkt G × H 2-pobarvljiv, mora biti tudi vsaj eden od grafov G in H 2-pobarvljiv.

Naslednji primer sta dokazala El-Zahar in Sauer leta 1985 dolgo časa po formulaciji domneve: če je produkt G × H 3-pobarvljiv, mora biti tudi eden od grafov G ali H 3-pobarvljiv. Še posebej velja domneva kadar sta graf G ali H 4-pobarvljiva, saj neenakost   strogo velja, če je produkt G × H 3-pobarvljiv.[4] V peostalih primerih sta grafa v tenzorskem produktu vsaj 5-kromatična, napredek pa so dosegli le za zelo omejene primere.

Šibka Hedetniemijeva domnevaUredi

Naslednja funkcija (znana kot Poljak-Rödlova funkcija) meri kako majhno je lahko kromatično število produkta n-kromatičnih grafov:

 

Hedetniemijeva domneva je potem enakovredna izjavi, da je  .

Šibka Hedetniemijeva domneva pravi samo, da je funkcija   neomejena. Z drugimi besedami, če se tenzorski produkt dveh grafov lahko pobarva z malo barvami, mora to obsegati neko mejo za kromatično število enega od faktorjev.

Glavni rezultat, ki so ga neodvisno izboljšali Svatopluk Poljak, James H. Schmerl in Zhu, pravi, da, če je funkcija   omejena, je omejena največ za kromatično število 9.[5] Tako bi dokaz Hedetniemijeve domneve za 10-kromatične grafe obsegal tudi šibko Hedetniemijevo domnevo za vse grafe.

Multiplikativni grafiUredi

Domneva se obravnava v splošnejšem kontekstu homomorfizmov grafov, še posebej zaradi zanimivih povezav s kategorijo grafov (z grafi kot objekti in homomorfizmi kot puščicami). Za poljubni fiksni graf K se obravnava graf G, ki dodovoljuje homomorfizem h grafu K, kar se napiše kot GK. Takšni grafi se imenujejo tudi K-pobarvljivi grafi. To posplošuje običajno predstavo barvanja grafov, saj sledi iz definicije, da je k-barvanje enako Kk-barvanju (homomorfizmu v polni graf na k točkah).

Graf K se imenuje multiplikativen, da, če za poljubna dva grafa G in H velja G × HK, potem od tod izhaja, da velja GK ali HK. Kakor pri klasičnem barvanju vedno velja obratna posledica: če je graf G (ali simetrično graf H) K-pobarvljiv, je enostavno produkt G × H K-pobarvan s pomočjo enakih vrednosti neodvisno od grafa H. Hedetniemijeva domneva je potem enakovredna izjavi, da je vsak polni graf multiplikativen.

Zgornji znani primeri so enakovredni izjavi, da so K1, K2 in K3 multiplikativni. Primer za K4 je nerešen. Na drugi strani so dokaz El-Zaharja in Sauerja[4] posplošili Häggkvist, Hell, Miller in Neumann-Lara leta 1988 in pokazali, da so vsi ciklični grafi multiplikativni.[6] Kasneje je Tardiff leta 2005 dokazal splošneje, da so vse ciklične klike Kn/k z n/k < 4 multiplikativne.[7] Glede na ciklično kromatično število χc to pomeni, da če velja χc(G×H) < 4, potem velja χc(G×H) = min {χc(G), χc(G)} .

Zgledi nemultiplikativnih grafov se lahko skonstruirajo iz dveh grafov G in H, ki nista primerljiva v redu homomorfizma (pri čemer ne velja GH niti HG). V tem primeru, če je K = G × H, trivialno izhaja G × HK, vendar tako G ali H ne moreta dovoljevati homomorfizma v K, ker bi sestavljena s projekcijo KH ali KG vodila do protislovja.

Eksponentni grafUredi

Ker je tenzorski produk grafov produkt teorije kategorij v kategoriji grafov (z grafi kot objekti in homomorfizmi kot puščicami), se lahko domneva na novo formulira glede na naslednjo konstrukcijo na grafih K in G. Eksponentni graf KG je graf z vsemi funkcijami V(G)V(K) kot točkami (ne samo homomorfizmi) in dvema funkcijama f in g, sosednjima kadar je

f(v) sosednja z g(v') v K za vse sosednje točke v,v ' grafa G.

Pri funkciji f še posebej obstaja zanka (je sosednja sama s seboj) tedaj in le tedaj, če funkcija da homomorfizem iz G v K. Ali drugače, med f in g obstaja povezava kadarkoli dve funkciji definirata homomorfizem iz G × K2 (dvodelno dvojno pokritje G) h K.

Eksponentni graf je eksponencial v kategoriji grafov. To pomeni, da homomorfizmi iz G × H v graf K odgovarjajo homomorfizmom iz H v KG. Velja še naprej, da obstaja homomorfizem eval : G × KGK, dan z eval(v,f) = f(v). Te značilnosti dovoljujejo sklep, da je multiplikativnost K enakovredna izjavi El-Zaharja in Sauerja:[4]

graf G ali KG je K-pobarvljiv za vsak graf G.

Hedetniemijeva domneva se lahko z drugimi besedami obravnava kot izjava na eksponentnih grafih: za vsako celo število k je graf KkG ali k-pobarvljiv, ali pa vsebuje zanko (kar pomeni, da je graf G k-pobarvljiv). Homomorfizmi eval : G × KkGKk se lahko imajo za najmočnejše primere Hedetniemijeve domneve: če je bil G × H protiprimer, bo tudi G × KkG.

PosplošitveUredi

Domneva posplošena na usmerjene grafe ima enostavne protiprimere, kakor sta odkrila Poljak in Rödl.[5] Tukaj je kromatično število usmerjenega grafa le kromatično število osnovnega grafa, tenzorski produkt pa ima natanko polovico števila povezav (za usmerjene povezave gg' v G in hh' v H ima tenzorski produkt G × H le eno povezavo, iz (g, h) v (g', h'), produkt osnovnih neusmerjenih grafov pa bi imel tudi povezavo med(g, h') in (g', h)). Izkaže se vseeno, da je šibka Hedetniemijeva domneva enakovredna pri usmerjenih in neusmerjenih grafih.[8]

Problema se ne da posplošiti na neskončne grafe: Hajnal je leta podal zgled dveh neskončnih grafov, ki sta vsak zase zahtevala neštevno mnogo barv, tako da se je njun produkt lahko pobarval samo s števno mnogo barvami.[9] Rinot je leta 2013 dokazal, da v konstruktibilnem univerzumu za vsako neskončno kardinalno število   obstaja par grafov s kromatičnim številom večjim od  , tako da se njun produkt še vedno lahko pobarva samo s števno mnogo barvami.[10]

Sorodni problemiUredi

Podobno neenakost za kartezični produkt grafov je dokazal Sabidussi leta 1957, drugi pa so ga večkrat ponovno neodvisno dokazali:[11][2][12]

 

Tudi za leksikografski produkt grafov je znana eksaktna formula. Duffus, Sands in Woodrow so leta 1985 uvedli dve močnejši domnevi, ki vsebujeta edinstveno pobarvljivost.[13]

SkliciUredi

ViriUredi

Osnovni viri
Pregledi in drugi viri