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; szerint a sejtést Albertson az American Mathematical Society 2007 októberében, Chicagóban tartott egy speciális ülésén fogalmazta meg. 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 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 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. 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.. 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 Ω(n4), vagy ami ezzel ekvivalens, minden k metszési számú gráf kromatikus száma O(k1/4). 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 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.; ; . 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 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,; . így ebből az irányból már nem lehet az Albertson-sejtést igazolni.
Fordítás
Jegyzetek
. . . . . As cited by . . .
Kategória:Topologikus gráfelmélet Kategória:Gráfok színezése Kategória:Sejtések