teljes gráfok kombinálásával kapott gráfok színezésével foglalkozó sejtés From Wikipedia, the free encyclopedia
A gráfelmélet területén az Erdős–Faber–Lovász-sejtés a gráfok színezésének egy megoldatlan problémája, amit Erdős Pálról, Vance Faberről és Lovász Lászlóról neveztek el, akik 1972-ben megfogalmazták.[1] Így szól:
A sejtés egy bizonyítását k elegendően nagy értékeire 2021-ben jelentették be Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku és Deryk Osthus.[2]
(Haddad & Tardif 2004) fogalmazta meg a bizottságok ülésrendjének problémáját: tegyük fel, hogy egy egyetemi tanszéken k bizottság létezik, mindegyiknek k tagja van, és minden bizottság ugyanabban a szobában ülésezik, melyben k szék található. Itt is tételezzük fel, hogy bármely két bizottság metszetében legfeljebb egy ember található. Lehetséges-e a bizottsági tagok leültetése olyan módon, hogy minden tag ugyanabban a székben maradhasson, bármelyik bizottság ülésezik is éppen? Ebben a megközelítésben a bizottsági tagok a gráfok csúcspontjainak felelnek meg, a bizottságok a teljes gráfoknak, a székek pedig a csúcsok színezéseinek.
Egy lineáris hipergráf (más néven részleges lineáris tér[3]) olyan hipergráf, melyben bármely két hiperél között legfeljebb egy közös csúcs van. Egy hipergráf akkor uniform, ha minden hiperéle ugyanannyi csúcsot köt össze. Az Erdős–Faber–Lovász-sejtés n méretű n klikkje úgy is értelmezhető, mint hiperélek egy n-uniform lineáris hipergráfban, melynek ugyanannyi csúcspontja van, mint a kiindulási gráf. Ilyen megközelítésben az Erdős–Faber–Lovász-sejtés azt mondja ki, hogy bármely n-uniform, n hiperéllel rendelkező lineáris hipergráfhoz tartozik olyan színezés, hogy n színnel ki lehet úgy színezni a csúcsokat, hogy minden hiperél mindegyik színű csúcsból éppen egyet tartalmazzon.[4]
Az egyszerű hipergráf (az egyszerű gráf mintájára) olyan hipergráf, melyben egyik hiperél sem tartalmazza a másikat (két csúcsot legfeljebb egy hiperél köt össze). Az Erdős–Faber–Lovász-sejtés gráfszínezési részében nyugodtan el lehet távolítani azokat a csúcsokat, amik egyetlen klikkhez tartoznak, hiszen a színezésük nem okoz problémát; ha ez megvan, a hipergráf minden klikkhez pontosan egy csúcsot és minden csúcshoz pontosan egy hiperélt tartalmaz, így alkotva egyszerű hipergráfot. A csúcsszínezés hipergráf-duálisa az élszínezés. Tehát az Erdős–Faber–Lovász-sejtés ekvivalens azzal az állítással, hogy bármely egyszerű n csúcsú hipergráf kromatikus indexe (élkromatikus száma) legfeljebb n.[5]
Az Erdős–Faber–Lovász-sejtés gráfja kifejezhető továbbá halmazok metszetgráfjaként: a gráf minden csúcsa megfelel a csúcsot tartalmazó klikkek halmaza, és két csúcs akkor van éllel összekötve, ha a megfelelő halmazok metszete nem üres. Ezt a leírást használva a sejtés így fogalmazható meg: ha valamely halmazcsalád összesen n elemű, és bármely két halmaz metszete legfeljebb egy elemet tartalmaz, akkor a halmazok metszetgráfja n-színezhető.[6]
Egy G gráf interszekciós számán az olyan halmazcsaládok minimális elemszámát értjük, melyek metszetgráfja G, vagy ami ezzel ekvivalens, az G élgráfú hipergráf minimális csúcsainak számát. (Klein & Margraf 2003) meghatározza egy gráf lineáris interszekciós számát; hasonlóan, hogy az a G élgráfú lineáris hipergráf minimális csúcsszáma legyen. Megfigyelésük szerint az Erdős–Faber–Lovász-sejtés ekvivalens azzal az állítással, hogy bármely gráf kromatikus száma kisebb vagy egyenlő, mint a lineáris interszekciós száma.
(Haddad & Tardif 2004) a klónok (speciális művelethalmazok) elméletén belül alkotott ekvivalens megfogalmazást.
Erdős Pál, Vance Faber és Lovász László fogalmazta meg 1972-ben a sejtést.[1] Erdős eredetileg 50 USD-t ajánlott a sejtés igazolásáért, később 500 dollárra emelte a jutalmat.[1][7]
(Chiang & Lawler 1988) igazolta, hogy a sejtésben szereplő gráfok kromatikus száma legfeljebb 3k/2 − 2, (Kahn 1992) ezt javította k + o(k)-ra.
Érdekes lehet a k csúcsú k db klikkből összeállított gráfok kromatikus számát megvizsgálni, anélkül is, hogy kikötnénk a klikkek közötti páronkénti metszetek számát. Ebben az esetben az uniógráf kromatikus száma legfeljebb 1 + k √k − 1 , és léteznek olyan gráfok, amikhez szükség is van éppen ennyi színre.[8]
A sejtés egy változatát, amit egész helyett frakcionális kromatikus számot használ kromatikus számok helyett már sikerült igazolni.[9]
Az egyszerű hipergráfok élszínezésének kontextusában (Hindman 1981) definiálja az egyszerű hipergráfhoz tartozó L számot, mint az olyan hipergráf-csúcsok számát, ami három vagy több csúcson átmenő hiperélhez tartozik. Megmutatja, hogy bármely fix L értékhez véges számításmennyiséggel meghatározható, hogy az összes, adott L értékű egyszerű hipergráfra igaz-e a sejtés. Az ötlet alapján igazolta is, hogy a sejtés valóban igaz az összes L ≤ 10 egyszerű hipergráfra. Gráfszínezés szempontjából ez azt igazolja, hogy a sejtés igaz olyan gráfokra, melyekben legfeljebb 10 olyan klikk van, aminek az egyik csúcsa 3 vagy több klikkbe tartozik. Ez n ≤ 10-re feltétlen igaz.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
