Vertex partitions of non-complete graphs into connected monochromatic k-regular graphs

详细信息    查看全文

• 作者：G&#xe1 ; bor N. S&#xe1 ; rkö ; zy^a ; ^b ; ^{gsarkozy@cs.wpi.edu"" rel=""nofollow} ; Stanley M. Selkow^a ; ^{sms@cs.wpi.edu"" rel=""nofollow} ; Fei Song^a ; ^{fes@cs.wpi.edu"" rel=""nofollow}
• 关键词：Vertex partitions ; Monochromatic ; none ; color ; black"" href=""/science?_ob=MathURL&_method=retrieve&_udi=B6V00-534W8M2-2&_mathId=mml17&_pii=S0012365X11002482&_issn=0012365X&_acct=C000050441&_version=1&_userid=1019
• 刊名：Discrete Mathematics
• 出版年：2011
• 出版时间：6 October 2011
• 年：2011
• 卷：311
• 期：18-19
• 页码：2079-2084
• 全文大小：213 K

文摘

In a landmark paper, Erdős et al. (1991) [3] proved that if G is a complete graph whose edges are colored with r colors then the vertex set of G can be partitioned into at most cr²logr monochromatic, vertex disjoint cycles for some constant c. Sárközy extended this result to non-complete graphs, and Sárközy and Selkow extended it to k-regular subgraphs. Generalizing these two results, we show that if G is a graph with independence number α(G)=α whose edges are colored with r colors then the vertex set of G can be partitioned into at most (αr)^{c(αrlog(αr)+k)} vertex disjoint connected monochromatick-regular subgraphs of G for some constant c.