Albertson-sejtés

A matematika, azon belül a gráfelmélet területén az Albertson-sejtés a gráfok kromatikus száma és metszési száma közötti bizonyítatlan összefüggés. Nevét a Smith College professzoráról, Michael O. Albertsonról kapta, aki 2007-ben megfogalmazta; ez a gráfok színezésével kapcsolatos sok sejtésének egyike. A sejtés állítása szerint az összes, n kromatikus számú gráf közül a K_n teljes gráf metszési száma a legalacsonyabb. Ezzel ekvivalens megfogalmazás szerint ha egy gráf a K_n-énél kevesebb metszéssel megrajzolható, akkor n-nél kevesebb színnel színezhető.

A minimális metszési szám sejtett képlete

Könnyen megmutatható, hogy a korlátos metszésű számok kromatikus száma is korlátos: a metsző élekhez különböző színeket kell rendelni, majd a megmaradó síkgráf a négyszín-tétel értelmében 4-színezhető. Az Albertson-sejtés a metszési szám és a színezés közti kvalitatív kapcsolatot kísérli meg precízebb, kvantitatív kapcsolattá alakítani. Richard K. Guy (1972) egy másik sejtése értelmében ugyanis a K_n teljes gráf metszési száma:

${\textrm {cr}}(K_{n})={\frac {1}{4}}\left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {n-2}{2}}\right\rfloor \left\lfloor {\frac {n-3}{2}}\right\rfloor .$

Ismert annak módszere, hogyan lehet teljes gráfokat pontosan ennyi metszéssel megrajzolni, a csúcsok két koncentrikus körön történő elhelyezésével; ami nem ismert, hogy vajon létezik-e ennél jobb, kevesebb metszéssel történő síkba rajzolás. Ezért az Albertson-sejtés erősebb megfogalmazása szerint minden n-kromatikus számú gráf metszési száma legalább akkora, mint az előbbi képlet jobb oldala. Ez az erősebb sejtés csak akkor igaz, ha mind Guy, mind Albertson eredeti sejtése igaznak bizonyul.

Aszimptotikus korlátok

A sejtés egy gyengébb, M. Schaefer által bizonyított változata szerint minden n kromatikus számú gráf metszési száma Ω(n⁴), vagy ami ezzel ekvivalens, minden k metszési számú gráf kromatikus száma O(k^1/4). (Albertson, Cranston & Fox 2009) ezeket a korlátokat egyszerűen bizonyította, összekötve azt a tényt, hogy minden minimális n-kromatikus gráf minimális fokszáma legalább n−1 (egyébként egy alacsony fokszámú csúcs eltávolításával a maradék gráf színezésével és az eltávolított csúcshoz egy megmaradó szín felhasználásával (n − 1)-színezni lehetne) a metszésiszám-egyenlőtlenséggel, ami szerint minden G = (V,E) gráfnak, melyben |E|/|V| ≥ 4 a metszési száma Ω(|E|³/|V|²). Ugyanezen okoskodás segítségével megmutatják, hogy ha létezik az Albertson-sejtés ellenpéldája, akkor n kromatikus szám esetén 4n-nél kevesebb csúcsból kell állnia.

Speciális esetek

Az Albertson-sejtés a n ≤ 4 esetre üres igazság: a K₄ metszési száma nulla, és minden gráf metszési száma nagyobb vagy egyenlő nullánál. Az Albertson-sejtés n = 5 esete megegyezik a négyszín-tétellel, mivel a K₅ egy metszésénél kevesebb metszést igénylő gráfok a síkbarajzolható gráfok, és a sejtés szerint ezek mind 4-kromatikusak. Számos szerzőcsoport erőfeszítése révén a sejtésről már ismert, hogy az összes n ≤ 18 esetre igaz. Luiz and Richter tetszőleges c ≥ 6 egész számra megmutatta, hogy létezik (c+1)-szín-kritikus gráfok olyan családja, ami nem tartalmazza a K_(c+1) teljes gráf felosztását, de metszési száma legalább K_(c+1).

Kapcsolódó sejtések

A kapcsolódó Hadwiger-sejtés a kromatikus szám és a nagyméretű klikkek gráfminorkénti létezését köti össze. A Hadwiger-sejtés Hajós György által kimondott változata szerint minden n-kromatikus gráf tartalmazza a K_n egy felosztását; ha ez igaz, abból az Albertson-sejtés is következne, mivel a teljes gráf metszési száma legalább akkora, mint bármely felosztásának metszési száma. A Hajós-sejtésre azonban már ismertek ellenpéldák, így ebből az irányból már nem lehet az Albertson-sejtést igazolni.

Fordítás

• Ez a szócikk részben vagy egészben az Albertson conjecture 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

• Albertson, Michael O.; Cranston, Daniel W. & Fox, Jacob (2009), "Colorings, crossings, and cliques", Electronic Journal of Combinatorics 16: R45, <http://www.combinatorics.org/Volume_16/PDF/v16i1r45.pdf>.
• Barát, János & Tóth, Géza (2010), "Towards the Albertson Conjecture", Electronic Journal of Combinatorics 17 (1): R73, <http://www.combinatorics.org/Volume_17/Abstracts/v17i1r73.html>.
• 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.
• Guy, Richard K. (1972), "Crossing numbers of graphs", in Alavi, Y.; Lick, D. R. & White, A. T., Graph Theory and Applications: Proceedings of the Conference at Western Michigan University, Kalamazoo, Mich., May 10–13, 1972, New York: Springer-Verlag, pp. 111–124. As cited by (Albertson, Cranston & Fox 2009).
• Oporowski, B. & Zhao, D. (2009), "Coloring graphs with crossings", Discrete Mathematics 309 (9): 2948–2951, DOI 10.1016/j.disc.2008.07.040.
• Luiz, Atílio & Richter, Bruce (2014), "Remarks on a conjecture of Barát and Tóth", Electronic Journal of Combinatorics 21 (1): P1.57, <http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p57>.