Search

We prove that there exists a function f(ℓ) such that the vertex set of every f(ℓ)-connected graph G can be partitioned into sets S and T such that each vertex in S has at least ℓ neighbours in T and both G[S] and G[T] are ℓ-connected. This implies that there exists a function g(ℓ,H) such that every g(ℓ,H)-connected graph contains a subdivision TH of H so that G−V(TH) is ℓ-connected. We also prove an analogue with connectivity replaced by minimum degree. Furthermore, we show that there exists a function h(ℓ) such that the vertex set of every graph G of minimum degree at least h(ℓ) can be partitioned into sets S and T such that both G[S] and G[T] have minimum degree at least ℓ and the bipartite subgraph between S and T has average degree at least ℓ.

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 Hajos 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 max{δ(H), 3} and girth at least 166 log|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|.