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: (A matematika további megoldatlan problémái) |
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, Kk.
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.[1]
Ekvivalens megfogalmazások
szerkesztésAz 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 Kk 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 Kk 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 Kk teljes gráfot kell létrehoznia az élösszehúzásnak, ha az összehúzandó halmazok összefüggőek.
Ha Fk azt a gráfcsaládot jelöli, melyre igaz, hogy minden Fk-beli gráf minden minora (k − 1)-színezhető, akkor a Robertson–Seymour-tételből következik, akkor Fk 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 Kk teljes gráfot.
A G gráfhoz tartozó Hadwiger-szám, h(G) megegyezik annak a legnagyobb Kk 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).[1] 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
szerkesztésA 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 K2 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 K3 minor.
A sejtést bevezető cikkben Hadwiger bizonyította is sejtését a k ≤ 4 esetekre. A K4 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 K5-ö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 K5 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 K5-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.[2] 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 K7-et, vagy a K4,4-et és a K3,5-öt.[3]
Minden G gráfban van olyan csúcs, ami legfeljebb O(h(G) √log h(G)) éllel érintkezik,[4] 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
szerkesztésHajó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 Kk 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.[5] (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 / log2 n, és hogy legnagyobb klikkfelosztásában legfeljebb cn1/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.[1]
(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 K5-minormentes gráfokra sem teljesül.[6] Általánosabban, minden t ≥ 1-re léteznek gráfok, melyek Hadwiger-száma 3t + 1 és melyek listakromatikus száma 4t + 1.[7]
Gerards és Seymour sejtése szerint minden k kromatikus számú G gráf tartalmazza a Kk 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 Kk 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 Kk minor nélküli gráf kromatikus száma χ(G) = O(k √log k).[8]
Néhány G-re vonatkozó további feltétel teljesülésekor lehetőség nyílhat Kk-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.[9]
Fordítás
szerkeszté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
szerkesztés- ↑ a b c (Bollobás, Catlin & Erdős 1980).
- ↑ (Nešetřil & Thomas 1985).
- ↑ A K7 vagy K3,5 minor létezését Ken-ichi Kawarabayashi mutatta meg, (Kawarabayashi & Toft 2005) pedig a K7 vagy K4,4 minor létezését igazolta.
- ↑ (Kostochka 1984). Az O a kifejezésben a nagy ordó jelölésre utal.
- ↑ (Yu & Zickfeld 2006).
- ↑ (Voigt 1993); (Thomassen 1994).
- ↑ (Barát, Joret & Wood 2011).
- ↑ (Geelen et al. 2006); Kawarabayashi (Journal of Combinatorial Theory, Series B Volume 99, Issue 1, January 2009, Pages 20-29).
- ↑ Pegg, Ed, Jr. (2002), "Book Review: The Colossal Book of Mathematics", Notices of the American Mathematical Society 49 (9): 1084–1086, doi:10.1109/TED.2002.1003756, <http://www.ams.org/notices/200209/rev-pegg.pdf>.
- 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 Kk-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 K7 or K4,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 K6-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.