Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4656792 | Journal of Combinatorial Theory, Series B | 2015 | 18 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
József Balogh, Hong Liu, Maryam Sharifzadeh,