Hadwiger-sejtés (gráfelmélet)

Ez a szócikk Hadwiger gráfelméleti sejtéséről szól. Lásd még: Hadwiger-sejtés (kombinatorikus geometria)

A matematika megoldatlan problémája: Tartalmazza-e minden $k$ kromatikus számú gráf a $k$-csúcsú teljes gráfot minorként? (A matematika további megoldatlan problémái)

Az ábrán látható gráf színezéséhez négy színre van szükség; látható továbbá négy összefüggő részgráfja, melyek minorként összehúzva teljes gráfot adnak, illusztrálva ezzel a Hadwiger-sejtés k = 4 esetét.

A matematika, azon belül a gráfelmélet területén a Hadwiger-sejtés szerint ha egy G irányítatlan gráf minden (jó) színezéséhez k vagy több színre van szükség (azaz kromatikus száma legalább k), akkor található G-ben k olyan összefüggő, diszjunkt részgráf, melyek páronként mind éllel vannak összekötve. Ha minden ilyen részgráfon belül élösszehúzást végzünk, akkor a részgráfok egy-egy csúccsá omlanak össze, ami azt jelenti, hogy a G gráf minorja a k csúcsú teljes gráf, K_k.

Ez a Hugo Hadwiger által 1943-ban kimondott sejtés a négyszíntétel messzemenő általánosítása, ami jelenleg is messze áll a megoldástól. (Bollobás, Catlin & Erdős 1980) „a gráfelmélet egyik legmélyebb megoldatlan problémájának” nevezi.

Ekvivalens megfogalmazások

Az előzővel ekvivalens, kontrapozíciós formában megfogalmazott állítás szerint ha a G-t nem lehet élösszehúzások sorozatával a K_k teljes gráfba átvinni, akkor G k − 1 színnel színezhető.

Vegyük észre, hogy bármely G gráf minimális k-színezésében az egyes színosztályokat egy-egy csúccsá összehúzva a K_k teljes gráfot kapjuk. Ez az összehúzási folyamat azonban nem állítja elő G minorát, mivel (definíció szerint) az azonos színosztályba tartozó csúcsok között nincsenek élek, ezért az itt alkalmazott összehúzás nem a minorok definíciójában szereplő élösszehúzás művelet. Hadwiger sejtése szerint úgy is működnie kell, azaz K_k teljes gráfot kell létrehoznia az élösszehúzásnak, ha az összehúzandó halmazok összefüggőek.

Ha F_k azt a gráfcsaládot jelöli, melyre igaz, hogy minden F_k-beli gráf minden minora (k − 1)-színezhető, akkor a Robertson–Seymour-tételből következik, akkor F_k tiltott minorainak véges halmazával karakterizálható. Hadwiger sejtése azt mondja, ki, hogy ez a halmaz egyetlen tiltott minort tartalmaz, méghozzá a K_k teljes gráfot.

A G gráfhoz tartozó Hadwiger-szám, h(G) megegyezik annak a legnagyobb K_k teljes gráfnak a k méretével, ami G-nek minora (vagy ezzel ekvivalensen, előállítható G éleinek összehúzásával). Úgy is ismert, mint G összehúzási klikkszáma (contraction clique number). A Hadwiger-sejtés így egyszerű algebrai alakban is megfogalmazható: χ(G) ≤ h(G), ahol χ(G) G kromatikus számát jelöli.

Speciális esetek és részeredmények

A k = 2 eset triviális: egy gráfhoz pontosan akkor szükséges egynél több szín, ha van éle, és ez az él maga is egy K₂ minor. A k = 3 eset szintén elég könnyű: a három színt igénylő gráfok a nem páros gráfok, melyek mindegyike rendelkezik páratlan körrel, ami összehúzható 3-körré, ami éppen a K₃ minor.

A sejtést bevezető cikkben Hadwiger bizonyította is sejtését a k ≤ 4 esetekre. A K₄ minor nélküli gráfok a soros-párhuzamos gráfok és azok részgráfjai. Az ilyen gráfok mindegyikében található olyan csúcs, ami legfeljebb két éllel érintkezik; a gráfból a csúcs eltávolítása után kapott maradék rekurzívan 3-színezhető, majd a csúcs visszatehető és szintén színezhető. Mivel az eltávolított csúcshoz legfeljebb két él kapcsolódik, a három szín egyike mindig elérhető lesz a csúcs visszarakásakor.

A sejtés k = 5-re való teljesüléséből következik a négyszíntétel: mivel, ha a sejtés igaz, minden legalább 5 színt igénylő gráf tartalmazná a K₅-öt minorként és ezért (a Wagner-tétel értelmében) nem lenne síkba rajzolható. Klaus Wagner 1937-ben bebizonyította, hogy a k = 5 eset valójában ekvivalens a négyszíntétellel, ezért most már biztosan tudjuk, hogy igaz. Wagner megmutatta, hogy az összes K₅ minor nélküli gráf felbontható a klikk-összeg művelet segítségével olyan részekre, melyek vagy maguk is síkba rajzolhatók vagy nyolc csúcsú Möbius-létrák, és ezek egymástól függetlenül mind 4-színezhetők, így a K₅-minormentes gráfok színezhetősége a síkbeli részek 4-színezhetőségéből következik.

(Robertson, Seymour & Thomas 1993) szintén a négyszíntétel felhasználásával bizonyította a sejtést a k = 6 esetre; a bizonyítást tartalmazó cikk elnyerte az 1994-es Fulkerson-díjat. Bizonyításukból következik, hogy a síkgráfok egy háromdimenziós analógiájaként előálló láncmentesen beágyazható gráfok kromatikus száma legfeljebb öt. Az eredményből következik, hogy a sejtés igaz minden k ≤ 6 esetre, de a k > 6 esetről nem mond semmit.

A k = 7 eset kapcsán néhány részeredmény ismert: minden 7-kromatikus gráf minorként tartalmazza vagy a K₇-et, vagy a K_4,4-et és a K_3,5-öt.

Minden G gráfban van olyan csúcs, ami legfeljebb O(h(G) √log h(G)) éllel érintkezik, amiből következik, hogy egy mohó színezési algoritmus, ami eltávolítja ezt az alacsony fokszámú csúcsot, kiszínezi a megmaradó gráfot, majd visszateszi a törölt csúcsot és kiszínezi, az adott gráfot O(h(G) √log h(G)) színnel fogja színezni.

(Van der Zypen 2012) konstruált egy H összefüggő végtelen gráfot, melyre χ(H) = ω, de nem tartalmazza minorként a K_ω-t, ezzel megmutatva, hogy a sejtés megszámlálhatóan végtelen kromatikus számú gráfokra nem érvényes.

Általánosítások

Hajós György kimondta a Hadwiger-sejtés erősebb változatát, ami minorok helyett felosztásokat használ: azaz, minden k kromatikus számú gráf tartalmazza a K_k teljes gráf egy felosztását. Hajós sejtése igaz k ≤ 4-re, de (Catlin 1979) ellenpéldákat talált k ≥ 7-re, a k = 5 és k = 6 esetek még nyitottak. (Erdős & Fajtlowicz 1981) megfigyelése szerint a Hajós-sejtés nagyon elromlik véletlen gráfokat vizsgálva: tetszőleges ε > 0 esetén, ahogy a csúcsok száma, n, tart a végtelenbe, annak valószínűsége közelít egyhez, hogy egy n csúcsú véletlen gráf kromatikus száma ≥ (1/2 − ε)n / log₂ n, és hogy legnagyobb klikkfelosztásában legfeljebb cn^1/2 csúcs található valamely c konstansra. Ebben a kontextusban fontos megemlíteni, hogy annak a valószínűsége is tart egyhez, hogy egy n csúcsú véletlen gráf Hadwiger-száma eléri vagy meghaladja a kromatikus számát, tehát a Hadwiger-sejtés nagy valószínűséggel igaz a véletlen gráfokra; precízebben, a Hadwiger-szám nagy valószínűséggel az n/√log n konstansszorosa.

(Borowiecki 1993) feltette a kérdést, hogy vajon a Hadwiger-sejtés kiterjeszthető-e listaszínezésre. Bármely k ≤ 4-re igaz, hogy a k listakromatikus számú gráf tartalmaz k csúcsú klikket minorként. A síkba rajzolható gráfok maximális listakromatikus száma azonban 5 és nem 4, ezért ez a kiterjesztés már a K₅-minormentes gráfokra sem teljesül. Általánosabban, minden t ≥ 1-re léteznek gráfok, melyek Hadwiger-száma 3t + 1 és melyek listakromatikus száma 4t + 1.

Gerards és Seymour sejtése szerint minden k kromatikus számú G gráf tartalmazza a K_k teljes gráfot páratlan minorként. Egy ilyen struktúra leírható G k darab csúcsdiszjunkt részfáinak családjaként, melyek mindegyike 2-színezett oly módon, hogy bármely két részfa egyszínű éllel van összekötve. Bár a páratlan K_k minor nélküli gráfok nem feltétlenül ritkák, hasonló felső korlát vonatkozik rájuk, mint a standard Hadwiger-sejtésre: egy páratlan K_k minor nélküli gráf kromatikus száma χ(G) = O(k √log k).

Néhány G-re vonatkozó további feltétel teljesülésekor lehetőség nyílhat K_k-nál nagyobb minorok létezésének bizonyítására. Példa erre a W. T. Tutte által felvetett és 2001-ben Robertson, Sanders, Seymour és Thomas által állítólag bizonyított snark-tétel, miszerint minden legalább 4 élkromatikus számú 3-reguláris gráf tartalmazza a Petersen-gráfot minorként.

Fordítás

• Ez a szócikk részben vagy egészben a Hadwiger conjecture (graph theory) című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Barát, János; Joret, Gwenaël & Wood, David R. (2011), "Disproof of the list Hadwiger conjecture", Electronic Journal of Combinatorics 18 (1): P232, <http://www.combinatorics.org/Volume_18/Abstracts/v18i1p232.html>.
• Bollobás, B.; Catlin, P. A. & Erdős, Paul (1980), "Hadwiger's conjecture is true for almost every graph", European Journal of Combinatorics 1: 195–199, doi:10.1016/s0195-6698(80)80001-1, <http://www.renyi.hu/~p_erdos/1980-10.pdf>.
• Borowiecki, Mieczyslaw (1993), "Research problem 172", Discrete Mathematics 121: 235–236, DOI 10.1016/0012-365X(93)90557-A.
• Catlin, P. A. (1979), "Hajós's graph-colouring conjecture: variations and counterexamples", Journal of Combinatorial Theory, Series B 26 (2): 268–274, DOI 10.1016/0095-8956(79)90062-5.
• Erdős, Paul & Fajtlowicz, Siemion (1981), "On the conjecture of Hajós", Combinatorica 1 (2): 141–143, DOI 10.1007/BF02579269.
• Geelen, Jim; Gerards, Bert & Reed, Bruce et al. (2006), "On the odd-minor variant of Hadwiger's conjecture", Journal of Combinatorial Theory, Series B 99 (1): 20–29, DOI 10.1016/j.jctb.2008.03.006.
• Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Zürich 88: 133–143.
• Kawarabayashi, Ken-ichi, Minors in 7-chromatic graphs, Preprint.
• Kawarabayashi, Ken-ichi (2009), "Note on coloring graphs without odd K_k-minors", Journal of Combinatorial Theory, Series B 99 (4): 728, DOI 10.1016/j.jctb.2008.12.001. Journal of Combinatorial Theory, Series B, in press.
• Kawarabayashi, Ken-ichi & Toft, Bjarne (2005), "Any 7-chromatic graph has K₇ or K_4,4 as a minor", Combinatorica 25 (3): 327–353, DOI 10.1007/s00493-005-0019-1.
• Kostochka, A. V. (1984), "Lower bound of the Hadwiger number of graphs by their average degree", Combinatorica 4 (4): 307–316, DOI 10.1007/BF02579141.
• Nešetřil, Jaroslav & Thomas, Robin (1985), "A note on spatial representation of graphs", Commentationes Mathematicae Universitatis Carolinae 26 (4): 655–659, <http://dspace.dml.cz/handle/10338.dmlcz/106404>. Hozzáférés ideje: 2010-08-06 Archiválva 2011. július 18-i dátummal a Wayback Machine-ben.
• Robertson, Neil; Seymour, Paul & Thomas, Robin (1993), "Hadwiger's conjecture for K₆-free graphs", Combinatorica 13 (3): 279–361, doi:10.1007/BF01202354, <http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf>. Hozzáférés ideje: 2018-05-12.
• Thomassen, Carsten (1994), "Every planar graph is 5-choosable", Journal of Combinatorial Theory, Series B 62 (1): 180–181, DOI 10.1006/jctb.1994.1062.
• Van der Zypen, Dominic (2012), Hadwiger’s conjecture for graphs with infinite chromatic number.
• Voigt, Margit (1993), "List colourings of planar graphs", Discrete Mathematics 120 (1–3): 215–219, DOI 10.1016/0012-365X(93)90579-I.
• Wagner, Klaus (1937), "Über eine Eigenschaft der ebenen Komplexe", Mathematische Annalen 114: 570–590, DOI 10.1007/BF01594196.
• Yu, Xingxing & Zickfeld, Florian (2006), "Reducing Hajós' 4-coloring conjecture to 4-connected graphs", Journal of Combinatorial Theory, Series B 96 (4): 482–492, DOI 10.1016/j.jctb.2005.10.001.