Mit mondhatunk nagy kromatikus számú gráfok feszített részgráfjairól? Világos, hogy egy gráf kromatikus száma nagy, ha tartalmaz nagyméretű teljes részgráfot. Erdős és Hajnal ismert eredménye, hogy létezik tetszőlegesen nagy derékbőségű (legrövidebb kör mérete a gráfban) és nagy kromatikus számu gráf.
A témában Gyárfás azt a sejtést fogalmazta meg, hogy létezik a véges fák halmazán egy egész értékű $f$ függvény, hogy minden háromszög mentes $f(T)$ kromatikus számú gráf tartalmazza T-t, mint feszített részgráf. Egy jól ismert speciális eset, hogy egy $k$-kromatikus gráf részgráfként tartalmazza az összes $k$ pontú fát. Gyárfás és Lehel nemrég bizonyította, hogy minden $n$-uniform hipergráf, melynek kromatikus száma nagyobb mint $t$, tartalmazza az összes $n$-uniform $t$-élű hiperfát.
Az előadáson ezt a témát járnánk körül néhány állítást bizonyítva, néhány következményt csak kimondva.
Minden érdeklődőt szeretettel várunk,
Péter