摘要
In 1983 C. Thomassen [8] conjectured that for every k, g is an element of 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, Szemeredi, and the second author implies that the conjecture is true for every graph G with average d(G) >= c(k,g) log Delta(G).
We strengthen this and show that the conjecture holds for every graph G with average d(G) >= alpha (log log Delta(G))(beta) for some constants alpha, beta depending on k and g.
- 出版日期2011-11