An improved bound for vertex partitions by connected monochromatic K-regular graphs

摘要

Improving a result of Sárk?zy and Selkow, we show that for all integers r,k≥2 there exists a constant n0=n0(r,k) such that if n≥n0 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.