b"\n_START_ARTICLE_\nHedetniemijeva domneva\n_START_SECTION_\nZnani primeri\n_START_PARAGRAPH_\nVsak graf z neprazno mno\xc5\xbeico povezav zahteva vsaj dve barvi: \xc4\x8de grafa G in H nista 1-pobarvljiva, oziroma, da, \xc4\x8de vsebujeta povezavo, tudi njun produkt vsebuje povezavo in prav tako ni 1-pobarvljiv. \xc5\xa0e posebej domneva velja, \xc4\x8de sta grafa G ali H dvodelna, saj je njuno kromati\xc4\x8dno \xc5\xa1tevilo enako 1 ali 2._NEWLINE_Podobno, \xc4\x8de dva grafa G in H nista 2-pobarvljiva, oziroma nista dvodelna, potem oba vsebujeta cikel s sodo dol\xc5\xbeino. Ker produkt dveh sodih cikli\xc4\x8dnih grafov vsebuje sodi cikel, prav tako tudi produkt G \xc3\x97 H ni 2-pobarvljiv. Z drugimi besedami, \xc4\x8de je produkt G \xc3\x97 H 2-pobarvljiv, mora biti tudi vsaj eden od grafov G in H 2-pobarvljiv._NEWLINE_Naslednji primer sta dokazala El-Zahar in Sauer leta 1985 dolgo \xc4\x8dasa po formulaciji domneve: \xc4\x8de je produkt G \xc3\x97 H 3-pobarvljiv, mora biti tudi eden od grafov G ali H 3-pobarvljiv. \xc5\xa0e posebej velja domneva kadar sta graf G ali H 4-pobarvljiva, saj neenakost  strogo velja, \xc4\x8de je produkt G \xc3\x97 H 3-pobarvljiv. V peostalih primerih sta grafa v tenzorskem produktu vsaj 5-kromati\xc4\x8dna, napredek pa so dosegli le za zelo omejene primere.\n_START_SECTION_\nMultiplikativni grafi\n_START_PARAGRAPH_\nDomneva se obravnava v splo\xc5\xa1nej\xc5\xa1em kontekstu homomorfizmov grafov, \xc5\xa1e posebej zaradi zanimivih povezav s kategorijo grafov (z grafi kot objekti in homomorfizmi kot pu\xc5\xa1\xc4\x8dicami). Za poljubni fiksni graf K se obravnava graf G, ki dodovoljuje homomorfizem h grafu K, kar se napi\xc5\xa1e kot G \xe2\x86\x92 K. Tak\xc5\xa1ni grafi se imenujejo tudi K-pobarvljivi grafi. To posplo\xc5\xa1uje obi\xc4\x8dajno predstavo barvanja grafov, saj sledi iz definicije, da je k-barvanje enako K\xe2\x82\x96-barvanju (homomorfizmu v polni graf na k to\xc4\x8dkah)._NEWLINE_Graf K se imenuje multiplikativen, da, \xc4\x8de za poljubna dva grafa G in H velja G \xc3\x97 H \xe2\x86\x92 K, potem od tod izhaja, da velja G \xe2\x86\x92 K ali H \xe2\x86\x92 K. Kakor pri klasi\xc4\x8dnem barvanju vedno velja obratna posledica: \xc4\x8de je graf G (ali simetri\xc4\x8dno graf H) K-pobarvljiv, je enostavno produkt G \xc3\x97 H K-pobarvan s pomo\xc4\x8djo enakih vrednosti neodvisno od grafa H. Hedetniemijeva domneva je potem enakovredna izjavi, da je vsak polni graf multiplikativen._NEWLINE_Zgornji znani primeri so enakovredni izjavi, da so K\xe2\x82\x81, K\xe2\x82\x82 in K\xe2\x82\x83 multiplikativni. Primer za K\xe2\x82\x84 je nere\xc5\xa1en. Na drugi strani so dokaz El-Zaharja in Sauerja posplo\xc5\xa1ili H\xc3\xa4ggkvist, Hell, Miller in Neumann-Lara leta 1988 in pokazali, da so vsi cikli\xc4\x8dni grafi multiplikativni. Kasneje je Tardiff leta 2005 dokazal splo\xc5\xa1neje, da so vse cikli\xc4\x8dne klike Kn/k z n/k < 4 multiplikativne. Glede na cikli\xc4\x8dno kromati\xc4\x8dno \xc5\xa1tevilo \xcf\x87c to pomeni, da \xc4\x8de velja \xcf\x87c(G\xc3\x97H) < 4, potem velja \xcf\x87c(G\xc3\x97H)  = min {\xcf\x87c(G), \xcf\x87c(G)} ._NEWLINE_Zgledi nemultiplikativnih grafov se lahko skonstruirajo iz dveh grafov G in H, ki nista primerljiva v redu homomorfizma (pri \xc4\x8demer ne velja G \xe2\x86\x92 H niti H \xe2\x86\x92 G). V tem primeru, \xc4\x8de je K = G \xc3\x97 H, trivialno izhaja G \xc3\x97 H \xe2\x86\x92 K, vendar tako G ali H ne moreta dovoljevati homomorfizma v K, ker bi sestavljena s projekcijo K \xe2\x86\x92 H ali K \xe2\x86\x92 G vodila do protislovja.\n_START_SECTION_\nPosplo\xc5\xa1itve\n_START_PARAGRAPH_\nDomneva posplo\xc5\xa1ena na usmerjene grafe ima enostavne protiprimere, kakor sta odkrila Poljak in R\xc3\xb6dl. Tukaj je kromati\xc4\x8dno \xc5\xa1tevilo usmerjenega grafa le kromati\xc4\x8dno \xc5\xa1tevilo osnovnega grafa, tenzorski produkt pa ima natanko polovico \xc5\xa1tevila povezav (za usmerjene povezave g \xe2\x86\x92 g'  v G in h \xe2\x86\x92 h'  v H ima tenzorski produkt G \xc3\x97 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\xc5\xbee se vseeno, da je \xc5\xa1ibka Hedetniemijeva domneva enakovredna pri usmerjenih in neusmerjenih grafih._NEWLINE_Problema se ne da posplo\xc5\xa1iti na neskon\xc4\x8dne grafe: Hajnal je leta podal zgled dveh neskon\xc4\x8dnih grafov, ki sta vsak zase zahtevala ne\xc5\xa1tevno mnogo barv, tako da se je njun produkt lahko pobarval samo s \xc5\xa1tevno mnogo barvami. Rinot je leta 2013 dokazal, da v konstruktibilnem univerzumu za vsako neskon\xc4\x8dno kardinalno \xc5\xa1tevilo  obstaja par grafov s kromati\xc4\x8dnim \xc5\xa1tevilom ve\xc4\x8djim od , tako da se njun produkt \xc5\xa1e vedno lahko pobarva samo s \xc5\xa1tevno mnogo barvami."