Balanced Subdivisions of a Large Clique in Graphs with High Average Degree
Yan Wang · SIAM Journal on Discrete Mathematics · 2023
Abstract. In 1984, Thomassen conjectured that for every constant [Formula: see text], there exists [Formula: see text] such that every graph with average degree at least [Formula: see text] contains a balanced subdivision of a complete graph on [Formula: see text] vertices, i.e., a subdivision in which each edge is subdivided the same number of times. Recently, Liu and Montgomery confirmed Thomassen’s conjecture. We show that for every constant [Formula: see text], every graph with average degree at least [Formula: see text] contains a balanced subdivision of a complete graph of size at least [Formula: see text]. Note that this bound is almost optimal. Moreover, we show that every sparse expander with minimum degree at least [Formula: see text] contains a balanced subdivision of a complete graph of size at least [Formula: see text].