Balanced subdivisions of cliques in graphs

Abstract

Given a graph $H$, a balanced subdivision of $H$ is a graph obtained from $H$ by subdividing every edge the same number of times. In 1984, Thomassen conjectured that for each integer $k\ge 1$, high average degree is sufficient to guarantee a balanced subdivision of $K_k$. Recently, Liu and Montgomery resolved this conjecture. We give an optimal estimate up to an absolute constant factor by showing that there exists $c>0$ such that for sufficiently large $d$, every graph with average degree at least $d$ contains a balanced subdivision of a clique with at least $c{d}^{1/2}$ vertices. It also confirms a conjecture from Verstra{ë}te: every graph of average degree $c{d}^2$, for some absolute constant $c>0$, contains a pair of disjoint isomorphic subdivisions of the complete graph $K_d$. We also prove that there exists some absolute $c>0$ such that for sufficiently large $d$, every $C_4$-free graph with average degree at least $d$ contains a balanced subdivision of the complete graph $K_{cd}$, which extends a result of Balogh, Liu and Sharifzadeh.

arXiv comment18 pages, 2 figures