Publikace na Matematicko-fyzikální fakulta |
2011
Abstrakt
V roce 1983 Thomassen formuloval hypotézu, že pro každá přirozená čísla k a g existuje d takové, že každý graf s očekávaným stupněm alespoň d obsahuje podgraf s očekávaným stupněm alespoň k a girth g. Kuhn a Osthus v roce 2004 dokázali platnost hypotézy pro g=6. Článek přináší jiný důkaz pro tento případ založený na Furediho výsledcích pro hypergrafy.
Také jsme dokázali analogickou hypotézu pro orientované grafy.