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.. Így szól:
Vegyünk teljes gráfot, melyek mindegyikének pontosan csúcspontja van, és bármely két gráfnak pontosan egy közös csúcsa van, akkor a gráfok egyesítésével kapott gráf színnel színezhető.
A sejtés egy bizonyítását elegendően nagy értékeire 2021-ben jelentették be Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku és Deryk Osthus.;
Egyenértékű megfogalmazások fogalmazta meg a bizottságok ülésrendjének problémáját: tegyük fel, hogy egy egyetemi tanszéken bizottság létezik, mindegyiknek tagja van, és minden bizottság ugyanabban a szobában ülésezik, melyben 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érA „lineáris tér” itt nem vektortér értelemben értendő) 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 méretű klikkje úgy is értelmezhető, mint hiperélek egy -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 -uniform, hiperéllel rendelkező lineáris hipergráfhoz tartozik olyan színezés, hogy színnel ki lehet úgy színezni a csúcsokat, hogy minden hiperél mindegyik színű csúcsból éppen egyet tartalmazzon..
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ű csúcsú hipergráf kromatikus indexe (élkromatikus száma) legfeljebb .. ezzel ekvivalens problémát fogalmaz meg a halmazcsaládok nyelvén a hipergráfok helyett.
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 elemű, és bármely két halmaz metszete legfeljebb egy elemet tartalmaz, akkor a halmazok metszetgráfja -színezhető..
Egy gráf interszekciós számán az olyan halmazcsaládok minimális elemszámát értjük, melyek metszetgráfja , vagy ami ezzel ekvivalens, az élgráfú hipergráf minimális csúcsainak számát. meghatározza egy gráf lineáris interszekciós számát; hasonlóan, hogy az a é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.
a klónok (speciális művelethalmazok) elméletén belül alkotott ekvivalens megfogalmazást.
Történet, részeredmények Erdős Pál, Vance Faber és Lovász László fogalmazta meg 1972-ben a sejtést.. Erdős eredetileg 50 USD-t ajánlott a sejtés igazolásáért, később 500 dollárra emelte a jutalmat..
igazolta, hogy a sejtésben szereplő gráfok kromatikus száma legfeljebb , ezt javította -ra.
Kapcsolódó problémák Érdekes lehet a csúcsú 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 , és léteznek olyan gráfok, amikhez szükség is van éppen ennyi színre.; .
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..
Az egyszerű hipergráfok élszínezésének kontextusában definiálja az egyszerű hipergráfhoz tartozó 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 értékhez véges számításmennyiséggel meghatározható, hogy az összes, adott é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 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 -re feltétlen igaz.
Kapcsolódó szócikkek Erdős Pál sejtéseinek listája
Jegyzetek
. . . . Solutions by Ilias Kastanas, Charles Vanden Eynden, and Richard Holzsager, American Mathematical Monthly 100 (7): 692–693, 1992. . . . Corrected in JCTB 51 (2): 329, 1991, to add Tuza's name as coauthor. . .
. .
További információk Gócza Gergely: Erdős, Faber és Lovász sejtéséről (szakdolgozat, 2015)
Kategória:Gráfok színezése Kategória:Sejtések Kategória:Erdős Pál