Subdivisions of a large clique in C6-free graphs

被引：8

作者：

Balogh, Jozsef ^{[1
,2
]}

Liu, Hong ^{[2
]}

Sharifzadeh, Maryam ^{[2
]}

机构：

[1] Univ Szeged, Bolyai Inst, H-6720 Szeged, Hungary

[2] Univ Illinois, Dept Math Sci, Urbana, IL 61801 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2015年 / 112卷

关键词：

Subdivisions; Topological minors; Girth; Mader conjecture; Dependent random choice; BIPARTITE GRAPHS; CYCLE;

D O I：

10.1016/j.jctb.2014.11.004

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Mader conjectured that every C-4-free graph has a subdivision of a clique of order linear in its average degree. We show that every C-6-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-4-free graph with average degree cn(1/2) has a subdivision of a clique K-l with l = [c'n(1/2)] where every edge is subdivided exactly 3 times. (C) 2014 Elsevier Inc. All rights reserved.

引用

页码：18 / 35

页数：18

共 18 条

[1] Turan numbers of bipartite graphs and related Ramsey-Type questions
Alon, N
Krivelevich, M
Sudakov, B
[J]. COMBINATORICS PROBABILITY & COMPUTING, 2003, 12 (5-6) : 477 - 494
[2] [Anonymous], SURVEYS COMBINATORIC
[3] Proof of a conjecture of Mader, Erdos and Hajnal on topological complete subgraphs
Bollobás, B
Thomason, A
[J]. EUROPEAN JOURNAL OF COMBINATORICS, 1998, 19 (08) : 883 - 887
[4] Bondy J. A., 1974, Journal of Combinatorial Theory, Series B, V16, P97, DOI 10.1016/0095-8956(74)90052-5
[5] Erds P., 1979, GRAPH THEORY RELATED, P153
[6] Dependent Random Choice
Fox, Jacob
Sudakov, Benny
[J]. RANDOM STRUCTURES & ALGORITHMS, 2011, 38 (1-2) : 68 - 99
[7] C-6-free bipartite graphs and product representation of squares
Gyori, E
[J]. DISCRETE MATHEMATICS, 1997, 165 : 371 - 375
[8] GENERALIZATION OF N-FOLD RELATIONSHIP FOR GRAPHS
JUNG, HA
[J]. MATHEMATISCHE ANNALEN, 1970, 187 (02) : 95 - +
[9] KOML\OS J., 1994, COMB PROBAB COMPUT, V3, P247
[10] KOMLOS J., 1996, COMB PROBAB COMPUT, V5, P79

← 1 2 →