Article ID Journal Published Year Pages File Type
4656792 Journal of Combinatorial Theory, Series B 2015 18 Pages PDF
Abstract

Mader conjectured that every C4C4-free graph has a subdivision of a clique of order linear in its average degree. We show that every C6C6-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′c′ such that every C4C4-free graph with average degree cn1/2cn1/2 has a subdivision of a clique KℓKℓ with ℓ=⌊c′n1/2⌋ℓ=⌊c′n1/2⌋ where every edge is subdivided exactly 3 times.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,