NUK - logo
E-resources
Full text
Peer reviewed Open access
  • Disjoint isomorphic balance...
    Fernández, Irene Gil; Hyde, Joseph; Liu, Hong; Pikhurko, Oleg; Wu, Zhuo

    Journal of combinatorial theory. Series B, July 2023, 2023-07-00, Volume: 161
    Journal Article

    A classical result, due to Bollobás and Thomason, and independently Komlós and Szemerédi, states that there is a constant C such that every graph with average degree at least Ck2 has a subdivision of Kk, the complete graph on k vertices. We study two directions extending this result.•Verstraëte conjectured that a quadratic bound guarantees in fact two vertex-disjoint isomorphic copies of a Kk-subdivision.•Thomassen conjectured that for each k∈N there is some d=d(k) such that every graph with average degree at least d contains a balanced subdivision of Kk. Recently, Liu and Montgomery confirmed Thomassen's conjecture, but the optimal bound on d(k) remains open. In this paper, we show that a quadratic lower bound on average degree suffices to force a balanced Kk-subdivision. This gives the right order of magnitude of the optimal d(k) needed in Thomassen's conjecture. Since a balanced Kmk-subdivision trivially contains m vertex-disjoint isomorphic Kk-subdivisions, this also confirms Verstraëte's conjecture in a strong sense.