Erdős–Faber–Lovász-sejtés

teljes gráfok kombinálásával kapott gráfok színezésével foglalkozó sejtés
Az Erdős–Faber–Lovász-sejtés egy példája: egy négy-négy csúcsból álló négy klikkből alakított gráf, melyben bármely két klikk között pontosan egy közös csúcs van, négy színnel kiszínezhető.

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:

Vegyünk k teljes gráfot, melyek mindegyikének pontosan k 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 k színnel színezhető.

Egyenértékű megfogalmazásokSzerkesztés

(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[2]) 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.[3]

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.[4]

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ő.[5]

Egy G gráf interszekciós számán(wd) 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 az 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.

Történet, részeredményekSzerkesztés

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][6]

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

Kapcsolódó problémákSzerkesztés

É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.[7]

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.[8]

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.

Kapcsolódó szócikkekSzerkesztés

JegyzetekSzerkesztés

  1. a b c (Erdős 1981).
  2. A „lineáris tér” itt nem vektortér értelemben értendő
  3. (Romero & Sánchez Arroyo 2007).
  4. (Chiang & Lawler 1988). (Hindman 1981) ezzel ekvivalens problémát fogalmaz meg a halmazcsaládok nyelvén a hipergráfok helyett.
  5. (Hindman 1981).
  6. (Chung & Graham 1998).
  7. (Erdős 1991); (Horák & Tuza 1990).
  8. (Kahn & Seymour 1992).

További információkSzerkesztés