Albertson-sejtés

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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ő.

A minimális metszési szám sejtett képlete[szerkesztés]

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:

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.

Aszimptotikus korlátok[szerkesztés]

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.

Speciális esetek[szerkesztés]

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]

Kapcsolódó sejtések[szerkesztés]

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.

Fordítás[szerkeszté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.

Jegyzetek[szerkesztés]