Hedetniemijeva domneva

Zgled Hedetniemijeve domneve: tenzorski produkt cikličnih grafov $C_{5}\!\,$ in $C_{3}\!\,$ (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:

\chi (G\times H)=\min\{\chi (G),\chi (H)\}\!\,,

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 primeri

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 $\chi (g)\times H)\leq \min\{\chi (G),\chi (H)\}\!\,$ 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 domneva

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

f(n)=\min\{\chi (G\times H):\chi (G)=\chi (H)=n\}\!\,.

Hedetniemijeva domneva je potem enakovredna izjavi, da je $f(n)=n\!\,$ .

Šibka Hedetniemijeva domneva pravi samo, da je funkcija $f(n)\!\,$ 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 $f(n)\!\,$ 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 grafi

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 G → K. 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 K_k-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 × H → K, potem od tod izhaja, da velja G → K ali H → K. 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 K₁, K₂ in K₃ multiplikativni. Primer za K₄ 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 K_n/k z n/k < 4 multiplikativne.^[7] Glede na ciklično kromatično število χ_c to pomeni, da če velja $χ c (G \times H) < 4$ , potem velja $χ c (G \times 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 G → H niti H → G). V tem primeru, če je K = G × H, trivialno izhaja G × H → K, vendar tako G ali H ne moreta dovoljevati homomorfizma v K, ker bi sestavljena s projekcijo K → H ali K → G vodila do protislovja.

Eksponentni graf

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 $K G$ je graf z vsemi funkcijami $V(G) \to 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 × K₂ (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 K^G. Velja še naprej, da obstaja homomorfizem $eval : G \times K G \to K$ , 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 K^G 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 K_k^G ali k-pobarvljiv, ali pa vsebuje zanko (kar pomeni, da je graf G k-pobarvljiv). Homomorfizmi $eval : G \times K k G \to K k$ se lahko imajo za najmočnejše primere Hedetniemijeve domneve: če je bil G × H protiprimer, bo tudi G × K_k^G.

Posplošitve

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 g → g' v G in h → h' 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 $\kappa \!\,$ obstaja par grafov s kromatičnim številom večjim od $\kappa \!\,$ , tako da se njun produkt še vedno lahko pobarva samo s števno mnogo barvami.^[10]

Sorodni problemi

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

\chi (G\,\square \,H)=\max\{\chi (G),\chi (H)\}\!\,.

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]

Viri

Osnovni viri

Duffus, Dwight; Sands, B.; Woodrow, R. E. (1985), »On the chromatic number of the product of graphs«, Journal of Graph Theory, 9 (4): 487–495, doi:10.1002/jgt.3190090409, MR 0890239
El-Zahar, Mohamed; Sauer, Norbert (1985), »The chromatic number of the product of two 4-chromatic graphs is 4«, Combinatorica, 5 (2): 121–126, doi:10.1007/BF02579374, MR 0815577
Foniok, Jan; Tardif, Claude (9. avgust 2016), Hedetniemi's conjecture and adjoint functors in thin categories, arXiv:1608.02918
Häggkvist, R.; Hell, Pavol; Miller, D. J.; Neumann-Lara, Victor (1988), »On multiplicative graphs and the product conjecture«, Combinatorica, 8 (1): 63–74, doi:10.1007/BF02122553, MR 0951994
Hajnal, András (1985), »The chromatic number of the product of two ℵ₁ chromatic graphs can be countable«, Combinatorica, 5 (2): 137–140, doi:10.1007/BF02579376, MR 0815579
Hedetniemi, Stephen Travis (1966), Homomorphisms of graphs and automata, Technical Report 03105-44-T, Univerza Michigana
Poljak, Svatopluk; Rödl, Vojtěch (1981), »On the arc-chromatic number of a digraph«, Journal of Combinatorial Theory, Series B, 31 (2): 190–198, doi:10.1016/S0095-8956(81)80024-X
Rinot, Assaf (2013), Hedetniemi's conjecture for uncountable graphs, arXiv:1307.6841, Bibcode:2013arXiv1307.6841R
Sabidussi, Gert (1957), »Graphs with given group and given graph-theoretical properties«, Canadian Journal of Mathematics, 9: 515–525, doi:10.4153/CJM-1957-060-7, MR 0094810
Šitov, Jaroslav Nikolajevič (Maj 2019), Counterexamples to Hedetniemi's conjecture, arXiv:1905.02167
Tardif, Claude (2005), »Multiplicative graphs and semi-lattice endomorphisms in the category of graphs«, Journal of Combinatorial Theory, Series B, 95 (2): 338–345, doi:10.1016/j.jctb.2005.06.002
Tardif, Claude; Wehlau, David (2006), »Chromatic numbers of products of graphs: The directed and undirected versions of the Poljak-Rödl function«, Journal of Graph Theory, 51 (1): 33–36, doi:10.1002/jgt.20117

Pregledi in drugi viri

Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8
Kalai, Gil (10. maj 2019), »A sensation in the morning news – Yaroslav Shitov: Counterexamples to Hedetniemi's conjecture«, Combinatorics and More
Klavžar, Sandi (1996), »Coloring graph products: a survey«, Discrete Mathematics, 155 (1–3): 135–145, doi:10.1016/0012-365X(94)00377-U, MR 1401366
Potanov, Vladimir (30. maj 2019), »В поисках хроматического числа«, N+1 (v ruščini), pridobljeno 30. maja 2019
Sauer, Norbert (2001), »Hedetniemi's conjecture: a survey«, Discrete Mathematics, 229 (1–3): 261–292, doi:10.1016/S0012-365X(00)00213-2, MR 1815610
Tardif, Claude (2008), »Hedetniemi's conjecture, 40 years later« (PDF), Graph Theory Notes of New York, 54: 46–57, MR 2445666, arhivirano iz prvotnega spletišča (PDF) dne 12. julija 2021, pridobljeno 1. julija 2019
Zhu, Xuding (1998), »A survey on Hedetniemi's conjecture«, Taiwanese J. Math., 2 (1): 1–24, MR 1609464

[shitov_2019-1] Šitov (2019).

[potanov_2019-2] 2,0 ^2,1 Potanov (2019).

[kalai_2019-3] Kalai (2019).

[el-zahar_1985-4] 4,0 ^4,1 ^4,2 El-Zahar; Sauer (1985).

[poljak_1981-5] 5,0 ^5,1 Poljak; Rödl (1981).

[haggkvist_1988-6] Häggkvist idr. (1988).

[tardiff_2005-7] Tardif (2005).

[tardiff_2006-8] Tardif; Wehlau (2006).

[hajnal_1985-9] Hajnal (1985).

[rinot_2013-10] Rinot (2013).

[sabidussi_1957-11] Sabidussi (1957).

[foniok_2016-12] Foniok; Tardif (2016).

[duffus_1985-13] Duffus; Sands; Woodrow (1985).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]