Gyárfás–Sumner-sejtés

Sablon:Megoldatlan A matematika, azon belül a gráfelmélet területén a Gyárfás–Sumner-sejtés azt állítja, hogy tetszőleges $T$ fát és $K$ teljes gráfot választva, a feszített részgráfként sem $T$-t, sem $K$-t nem tartalmazó gráfok konstans számú színnel jól színezhetők. Ezzel ekvivalens megfogalmazás szerint, a $T$- és $K$-mentes gráfok $\chi$-korlátosak.Sablon:R A sejtés nevét Gyárfás Andrásról és David Sumnerről kapta, akik egymástól függetlenül 1975-ben, illetve 1981-ben megfogalmazták.Sablon:R Jelenleg bizonyítatlan.Sablon:R

A sejtésben nem lehetséges $T$-t kört tartalmazó gráfra cserélni. Ahogy Erdős Pál és Hajnal András megmutatták, léteznek tetszőlegesen magas kromatikus számú, ugyanakkor tetszőlegesen nagy girthű háromszögmentes gráfok.Sablon:R Ezen gráfok felhasználásával előállíthatók olyan gráfok, amik elkerülnek bármely fixen választott, kört tartalmazó gráfot és (2 csúcsnál nagyobb) klikket feszített részgráfként, de tetszőlegesen választott értéknél magasabb a kromatikus számuk.Sablon:R

A sejtést bizonyították néhány speciálisan megválasztott $T$-re, így útgráfokra,Sablon:R csillagokra és kettő sugarú fákra.Sablon:R Ismert az is, hogy azok a gráfok, melyek nem tartalmaznak bármely konkrét $T$ fát felosztásként, $\chi$-korlátosak.Sablon:R

Fordítás

• Sablon:Fordítás

További információk

• Graphs with a forbidden induced tree are chi-bounded, Open Problem Garden