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

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

► We study monochromatic partitions of non-complete graphs. ► We partition by monochromatic connected kk-regular subgraphs. ► We generalize earlier results.