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 条

[21] k-Regular partitions and overpartitions with bounded part differences
Bernard L. S. Lin
Saisai Zheng
The Ramanujan Journal, 2021, 56 : 685 - 695
[22] K K,K IS (K-1, 1)-CRITICAL FOR K-REGULAR K-CONNECTED GRAPHS
ALDRED, REL
JIA, RZ
ARS COMBINATORIA, 1988, 26B : 247 - 248
[23] k-regular factors and semi-k-regular factors in graphs
Kotani, K
DISCRETE MATHEMATICS, 1998, 186 (1-3) : 177 - 193
[24] On the threshold for k-regular subgraphs of random graphs
Paweł Prałat
Jacques Verstraëte
Nicholas Wormald
Combinatorica, 2011, 31 : 565 - 581
[25] SPECTRAL DIAMETER ESTIMATES FOR K-REGULAR GRAPHS
QUENELL, G
ADVANCES IN MATHEMATICS, 1994, 106 (01) : 122 - 148
[26] On the threshold for k-regular subgraphs of random graphs
Pralat, Pawel
Verstraete, Jacques
Wormald, Nicholas
COMBINATORICA, 2011, 31 (05) : 565 - 581
[27] Longest Cycles in 3-Connected k-Regular Claw-Free Graphs
李国君
数学进展, 1993, (01) : 88 - 89
[28] On k-regular edge connectivity of chemical graphs
Ediz, Suleyman
Ciftci, Idris
MAIN GROUP METAL CHEMISTRY, 2022, 45 (01) : 106 - 110
[29] A sharp lower bound on the independence number of k-regular connected hypergraphs with rank R
Tang, Zhongzheng
Zou, Haoyang
Diao, Zhuo
ACTA INFORMATICA, 2025, 62 (01)
[30] 2-CONNECTED K-REGULAR GRAPHS ON AT MOST 3k+3 VERTICES TO BE HAMILTONIAN
朱永津
刘振宏
俞正光
Science Bulletin, 1985, (09) : 1269 - 1269

← 1 2 3 4 5 →