An Improved Bound for Vertex Partitions by Connected Monochromatic K-Regular Graphs

被引：9

作者：

Sarkoezy, Gabor N. ^{[1
]}

Selkow, Stanley M. ^{[2
]}

Song, Fei ^{[1
]}

机构：

[1] Worcester Polytech Inst, Dept Comp Sci, Worcester, MA 01609 USA

[2] Hungarian Acad Sci, Comp & Automat Res Inst, H-1518 Budapest, Hungary

来源：

JOURNAL OF GRAPH THEORY | 2013年 / 73卷 / 02期

基金：

美国国家科学基金会;

关键词：

vertex partitions; regulatory lemma; BLOW-UP LEMMA; CYCLES;

D O I：

10.1002/jgt.21661

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Improving a result of Sarkozy and Selkow, we show that for all integers r,k2 there exists a constant n0=n0(r,k) such that if nn0 and the edges of the complete graph Kn are colored with r colors then the vertex set of Kn can be partitioned into at most 100rlogr+2rk vertex disjoint connected monochromatic k-regular subgraphs and vertices. This is close to best possible. (c) 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 127145, 2013

引用

页码：127 / 145

页数：19

共 20 条

[1] Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles [J].

Allen, Peter .

COMBINATORICS PROBABILITY & COMPUTING, 2008, 17 (04) :471-486

[2]

[Anonymous], 1993, Com binatorics: Paul Erdos is eighty

[3] Partitioning a graph into a cycle and an anticycle, a proof of Lehel's conjecture [J].

Bessy, Stephane ;

Thomasse, Stephan .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2010, 100 (02) :176-180

[4]

Bollobas B., 2004, Extremal Graph Theory

[5]

Erds P., 1991, J COMB THEORY B, V51, P90

[6]

Erds P., 1959, ACTA MATH SCI HUNGAR, V10, P337

[7]

Gyarfas A., 1989, IRREGULARITIES PARTI, V8, P89

[8]

Gyarfas A., 2006, ALGORITHMS COMBINATO, P133

[9] Three-color Ramsey numbers for paths [J].

Gyarfas, Andras ;

Ruszinko, Miklos ;

Sarkozy, Gabor N. ;

Szemeredi, Endre .

COMBINATORICA, 2007, 27 (01) :35-69

[10] An improved bound for the monochromatic cycle partition number [J].

Gyarfas, Andras ;

Ruszinko, Miklos ;

Sarkozy, Gabor N. ;

Szemeredi, Endre .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (06) :855-873

← 1 2 →