Article ID Journal Published Year Pages File Type
4657000 Journal of Combinatorial Theory, Series B 2011 7 Pages PDF
Abstract

In 1983 C. Thomassen [8] conjectured that for every k,g∈N 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. A result of Pyber, Szemerédi, and the second author implies that the conjecture is true for every graph G with average .We strengthen this and show that the conjecture holds for every graph G with average for some constants α, β depending on k and g.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics