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

gráfelméleti sejtés
Ez a közzétett változat, ellenőrizve: 2022. november 10.
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 kromatikus számú gráf a -csúcsú teljes gráfot minorként?
(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.

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.

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és

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 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és

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 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(Glog 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(Glog 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és

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 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.
  1. a b c (Bollobás, Catlin & Erdős 1980).
  2. (Nešetřil & Thomas 1985).
  3. 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.
  4. (Kostochka 1984). Az O a kifejezésben a nagy ordó jelölésre utal.
  5. (Yu & Zickfeld 2006).
  6. (Voigt 1993); (Thomassen 1994).
  7. (Barát, Joret & Wood 2011).
  8. (Geelen et al. 2006); Kawarabayashi (Journal of Combinatorial Theory, Series B Volume 99, Issue 1, January 2009, Pages 20-29).
  9. 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>.