Disjoint isomorphic balanced clique subdivisions
Irene Gil Fernández, Joseph Hyde, Hong Liu, Oleg Pikhurko, Zhuo Wu
Abstract
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.
Topics & Concepts
CombinatoricsMathematicsSubdivisionConjectureDisjoint setsVertex (graph theory)GraphCliqueClique graphUpper and lower boundsDiscrete mathematicsLine graphGraph powerMathematical analysisHistoryArchaeologyLimits and Structures in Graph TheoryFinite Group Theory Researchgraph theory and CDMA systems