Premium
On a conjecture of Thomassen concerning subgraphs of large girth
Author(s) -
Dellamonica Domingos,
Koubek Václav,
Martin Daniel M.,
Rödl Vojtěch
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20534
Subject(s) - mathematics , combinatorics , conjecture , graph , girth (graph theory) , discrete mathematics
Abstract 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