






















In 1984, Thomassen conjectured that for every constant $k \in \mathbb{N}$, there exists $d$ such that every graph with average degree at least $d$ contains a balanced subdivision of a complete graph on $k$ 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 $0<c<1/2$, every graph with average degree at least $d$ contains a balanced subdivision of a complete graph of size at least $Ω(d^{c})$. Note that this bound is almost optimal. Moreover, we show that every sparse expander with minimum degree at least $d$ contains a balanced subdivision of a complete graph of size at least $Ω(d)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。