On a conjecture of Thomassen concerning subgraphs of large girth
Domingos Dellamonica, Vácłav Koubek, Daniel Michael Martin, Vojtěch Rödl · Journal of Graph Theory · 2010
In 1983 C. Thomassen conjectured that for every k, g∈ℕ there exists d such that any graph with average degree at least d contains a subgraph with average degree at least k and girth at least g. Kühn and Osthus [2004] proved the case g = 6. We give another proof for the case g = 6 which is based on a result of Füredi [1983] about hypergraphs. We also show that the analogous conjecture for directed graphs is true. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:316-331,2011