Decomposition of bounded degree graphs into C4-free subgraphs

被引：4

作者：

Kang, Ross J. ^{[1
]}

Perarnau, Guillem ^{[2
]}

机构：

[1] Radboud Univ Nijmegen, IMAPP, NL-6525 ED Nijmegen, Netherlands

[2] McGill Univ, Sch Comp Sci, Montreal, PQ, Canada

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2015年 / 44卷

关键词：

MULTICOLOR RAMSEY NUMBERS;

D O I：

10.1016/j.ejc.2014.09.009

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We prove that every graph with maximum degree Delta admits a partition of its edges into O(root Delta) parts (as Delta -> infinity) none of which contains C-4 as a subgraph. This bound is sharp up to a constant factor. Our proof uses an iterated random colouring procedure. (C) 2014 Elsevier Ltd. All rights reserved.

引用

页码：99 / 105

页数：7

共 13 条

[1]

Burr S.A., 1976, Ars Comb., V1, P167

[2] MULTICOLOR RAMSEY NUMBERS FOR COMPLETE BIPARTITE GRAPHS [J].

CHUNG, FRK ;

GRAHAM, RL .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1975, 18 (02) :164-169

[3]

Erdos P., 1938, MITT FORSCHUNGSINST, V2, P74

[4]

Füredi Z, 2013, BOLYAI SOC MATH STUD, V25, P169

[5]

Irving R. W., 1974, Discrete Mathematics, V9, P251, DOI 10.1016/0012-365X(74)90008-9

[6] Degree Ramsey numbers for cycles and blowups of trees [J].

Jiang, Tao ;

Milans, Kevin G. ;

West, Douglas B. .

EUROPEAN JOURNAL OF COMBINATORICS, 2013, 34 (02) :414-423

[7] Degree Ramsey Numbers of Graphs [J].

Kinnersley, William B. ;

Milans, Kevin G. ;

West, Douglas B. .

COMBINATORICS PROBABILITY & COMPUTING, 2012, 21 (1-2) :229-253

[8] Multi-color Ramsey numbers of even cycles [J].

Li, Yusheng ;

Lih, Ko-Wei .

EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (01) :114-118

[9]

Molloy M., 2002, ALGORITHM COMBINAT, V23

[10]

Nash-Williams C.S.J., 1964, J. Lond. Math. Soc, P12, DOI [10.1112/jlms/s1-39.1.12, DOI 10.1112/JLMS/S1-39.1.12]

← 1 2 →