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

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 c r 2 log r 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 ( α r log ( α r ) + k ) vertex disjoint connected monochromatic k -regular subgraphs of G for some constant c .