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 条

[31] A Dichotomy for k-Regular Graphs with {0,1}-Vertex Assignments and Real Edge Functions
Cai, Jin-Yi
Kowalczyk, Michael
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, 2010, 6108 : 328 - +
[32] Infinite families of infinite families of congruences for k-regular partitions
Carlson, Rowland
Webb, John J.
RAMANUJAN JOURNAL, 2014, 33 (03): : 329 - 337
[33] Infinitely Many Congruences for k-Regular Partitions with Designated Summands
da Silva, Robson
Sellers, James A.
BULLETIN OF THE BRAZILIAN MATHEMATICAL SOCIETY, 2020, 51 (02): : 357 - 370
[34] Infinitely Many Congruences for k-Regular Partitions with Designated Summands
Robson da Silva
James A. Sellers
Bulletin of the Brazilian Mathematical Society, New Series, 2020, 51 : 357 - 370
[35] A note on the higher order Turan inequalities for k-regular partitions
Craig, William
Pun, Anna
RESEARCH IN NUMBER THEORY, 2021, 7 (01)
[36] Infinite families of infinite families of congruences for k-regular partitions
Rowland Carlson
John J. Webb
The Ramanujan Journal, 2014, 33 : 329 - 337
[37] k-regular factors and semi-k-regular factors in bipartite graphs
Keiko Kotani
Annals of Combinatorics, 1998, 2 (2) : 137 - 144
[38] On defining numbers of k-chromatic k-regular graphs
Soltankhah, N
Mahmoodian, ES
ARS COMBINATORIA, 2005, 76 : 257 - 276
[39] k-Regular graphs with the circular chromatic index close to k
Candrakova, Barbora
Macajova, Edita
DISCRETE MATHEMATICS, 2014, 322 : 19 - 25
[40] Partition functions on k-regular graphs with {0,1}-vertex assignments and real edge functions
Cai, Jin-Yi
Kowalczyk, Michael
THEORETICAL COMPUTER SCIENCE, 2013, 494 : 63 - 74

← 1 2 3 4 5 →