Title of article :
Topological Minors in Graphs of Large Girth
Author/Authors :
Kühn، نويسنده , , Daniela and Osthus، نويسنده , , Deryk، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2002
Pages :
17
From page :
364
To page :
380
Abstract :
We prove that every graph of minimum degree at least r and girth at least 186 contains a subdivision of Kr+1 and that for r⩾435 a girth of at least 15 suffices. This implies that the conjecture of Hajós that every graph of chromatic number at least r contains a subdivision of Kr (which is false in general) is true for graphs of girth at least 186 (or 15 if r⩾436). More generally, we show that for every graph H of maximum degree Δ(H)⩾2, every graph G of minimum degree at least {Δ(H),3} and girth at least 166log∣H∣logΔ(H) contains a subdivision of H. This bound on the girth of G is best possible up to the value of the constant and improves a result of Mader, who gave a bound linear in ∣H∣.
Keywords :
subdivisions , girth , highly linked graphs , topological minors , Hajَs conjecture.
Journal title :
Journal of Combinatorial Theory Series B
Serial Year :
2002
Journal title :
Journal of Combinatorial Theory Series B
Record number :
1527107
Link To Document :
بازگشت