A matematika megoldatlan problémája: Az egy adott fát és egy adott klikket feszített részgráfként nem tartalmazó gráfok kromatikus száma korlátos-e? (A matematika további megoldatlan problémái)

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 ${\displaystyle T}$ fát és ${\displaystyle K}$ teljes gráfot választva, a feszített részgráfként sem ${\displaystyle T}$-t, sem ${\displaystyle K}$-t nem tartalmazó gráfok konstans számú színnel jól színezhetők. Ezzel ekvivalens megfogalmazás szerint, a ${\displaystyle T}$- és ${\displaystyle K}$-mentes gráfok ${\displaystyle \chi }$-korlátosak.^[1] 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.^[2][3] Jelenleg bizonyítatlan.^[4]

A sejtésben nem lehetséges ${\displaystyle 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.^[5] 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.^[1]

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

• Ez a szócikk részben vagy egészben a Gyárfás–Sumner conjecture című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

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