Subdivisions of a large clique in C6-free graphs

József Balogh; Hong Liu; Maryam Sharifzadeh

doi:10.1016/j.jctb.2014.11.004

Subdivisions of a large clique in C₆-free graphs

József Balogh, Hong Liu, Maryam Sharifzadeh

Mathematics

Research output: Contribution to journal › Article › peer-review

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 ℓ=⌊c^'n^1/2⌋ where every edge is subdivided exactly 3 times.

Original language	English (US)
Pages (from-to)	18-35
Number of pages	18
Journal	Journal of Combinatorial Theory. Series B
Volume	112
DOIs	https://doi.org/10.1016/j.jctb.2014.11.004
State	Published - May 1 2015

Keywords

Dependent random choice
Girth
Mader conjecture
Subdivisions
Topological minors

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Online availability

10.1016/j.jctb.2014.11.004

Library availability

Discover UIUC Full Text

Cite this

@article{a77797fa58a24a90b27a30724b4d61ba,

title = "Subdivisions of a large clique in C6-free graphs",

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

keywords = "Dependent random choice, Girth, Mader conjecture, Subdivisions, Topological minors",

author = "J{\'o}zsef Balogh and Hong Liu and Maryam Sharifzadeh",

note = "Publisher Copyright: {\textcopyright} 2014 Elsevier Inc.",

year = "2015",

month = may,

day = "1",

doi = "10.1016/j.jctb.2014.11.004",

language = "English (US)",

volume = "112",

pages = "18--35",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Subdivisions of a large clique in C6-free graphs

AU - Balogh, József

AU - Liu, Hong

AU - Sharifzadeh, Maryam

PY - 2015/5/1

Y1 - 2015/5/1

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

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

KW - Dependent random choice

KW - Girth

KW - Mader conjecture

KW - Subdivisions

KW - Topological minors

UR - http://www.scopus.com/inward/record.url?scp=84925070678&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84925070678&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2014.11.004

DO - 10.1016/j.jctb.2014.11.004

M3 - Article

AN - SCOPUS:84925070678

SN - 0095-8956

VL - 112

SP - 18

EP - 35

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -