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

共 50 条

[1] Vertex partitions by connected monochromatic k-regular graphs
Sárközy, GN
Selkow, SM
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2000, 78 (01) : 115 - 122
[2] Vertex partitions of non-complete graphs into connected monochromatic k-regular graphs
Sarkoezy, Gabor N.
Selkow, Stanley M.
Song, Fei
DISCRETE MATHEMATICS, 2011, 311 (18-19) : 2079 - 2084
[3] The connected vertex cover problem in k-regular graphs
Li, Yuchao
Wang, Wei
Yang, Zishen
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (02) : 635 - 645
[4] The connected vertex cover problem in k-regular graphs
Yuchao Li
Wei Wang
Zishen Yang
Journal of Combinatorial Optimization, 2019, 38 : 635 - 645
[5] ON THE K-DIAMETER OF K-REGULAR K-CONNECTED GRAPHS
HSU, DF
LUCZAK, T
DISCRETE MATHEMATICS, 1994, 133 (1-3) : 291 - 296
[6] On generalized k-diameter of k-regular k-connected graphs
Hou, XM
Wang, TM
TAIWANESE JOURNAL OF MATHEMATICS, 2004, 8 (04): : 739 - 745
[7] A polynomial algorithm determining cyclic vertex connectivity of k-regular graphs with fixed k
Liang, Jun
Lou, Dingjun
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 37 (03) : 1000 - 1010
[8] A polynomial algorithm determining cyclic vertex connectivity of k-regular graphs with fixed k
Jun Liang
Dingjun Lou
Journal of Combinatorial Optimization, 2019, 37 : 1000 - 1010
[9] Circuits through prescribed vertices in k-connected k-regular graphs
Häggkvist, R
Mader, W
JOURNAL OF GRAPH THEORY, 2002, 39 (02) : 145 - 163
[10] EMBEDDING K-REGULAR GRAPHS IN K+1-REGULAR GRAPHS
GARDINER, A
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 1983, 28 (DEC): : 393 - 400

← 1 2 3 4 5 →