Subdivisions of a large clique in C₆-free graphs

2013/12/21 by József Balogh, Hong Liu, Balogh, József +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO

paper · pdf · doi:10.48550/arxiv.1312.6213

17 pages

openalex publication_date 2013/12/21 · arxiv created 2014/11/15 · arxiv updated 2014/11/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Mader conjectured that every C₄-free graph has a subdivision of a clique of order linear in its average degree. We show that every C₆-free graph has such a subdivision of a large clique. We also prove the dense case of Mader's conjecture in a stronger sense, i.e. for every c, there is a c' such that every C₄-free graph with average degree cn^1/2 has a subdivision of a clique K_ℓ with ℓ=\lfloor c'n^1/2\rfloor where every edge is subdivided exactly 3 times.

Related

• Balanced subdivisions of a large clique in graphs with high average degree
• Balanced subdivisions of cliques in graphs
• Subdivisions in digraphs of large out-degree or large dichromatic number
• Balanced clique subdivisions and cycles lengths in K_{s, t}-free graphs
• Cliques in C₄-free graphs of large minimum degree