hu.wikipedia.org

Albertson-sejtés – Wikipédia

A Wikipédiából, a szabad enciklopédiából

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;[1] ez a gráfok színezésével kapcsolatos sok sejtésének egyike.[2] A sejtés állítása szerint az összes, n kromatikus számú gráf közül a Kn teljes gráf metszési száma a legalacsonyabb. Ezzel ekvivalens megfogalmazás szerint ha egy gráf a Kn-énél kevesebb metszéssel megrajzolható, akkor n-nél kevesebb színnel színezhető.

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 Kn teljes gráf metszési száma:

{\displaystyle {\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.[3] Ez az erősebb sejtés csak akkor igaz, ha mind Guy, mind Albertson eredeti sejtése igaznak bizonyul.

A sejtés egy gyengébb, M. Schaefer által bizonyított változata[3] szerint minden n kromatikus számú gráf metszési száma Ω(n4), vagy ami ezzel ekvivalens, minden k metszési számú gráf kromatikus száma O(k1/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|3/|V|2). 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.

Az Albertson-sejtés a n ≤ 4 esetre üres igazság: a K4 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 K5 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.[4][5] 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).[6]

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.[7] A Hadwiger-sejtés Hajós György által kimondott változata szerint minden n-kromatikus gráf tartalmazza a Kn 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,[8] így ebből az irányból már nem lehet az Albertson-sejtést igazolni.

  • 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.
  1. ↑ (Albertson, Cranston & Fox 2009) szerint a sejtést Albertson az American Mathematical Society 2007 októberében, Chicagóban tartott egy speciális ülésén fogalmazta meg.
  2. ↑ Hutchinson, Joan P. (June 19, 2009), In memory of Michael O. Albertson, 1946–2009: a collection of his outstanding conjectures and questions in graph theory, SIAM Activity group on Discrete Mathematics, <http://orion.math.iastate.edu/rymartin/dm-net/MOASIAM.pdf>.
  3. ↑ a b (Albertson, Cranston & Fox 2009).
  4. ↑ Ackerman, Eyal: On topological graphs with at most four crossings per edge, 2013. [2014. július 14-i dátummal az eredetiből archiválva].
  5. ↑ (Oporowski & Zhao 2009); (Albertson, Cranston & Fox 2009); (Barát & Tóth 2010).
  6. ↑ (Luiz & Richter 2014).
  7. ↑ (Barát & Tóth 2010).
  8. ↑ (Catlin 1979); (Erdős & Fajtlowicz 1981).