Monochromatic cycle partitions of edge‐colored graphs

In this article we study the monochromatic cycle partition problem for non‐complete graphs. We consider graphs with a given independence number α( G ) = α. Generalizing a classical conjecture of Erdös, Gyárfás and Pyber, we conjecture that if we r ‐color the edges of a graph G with α( G ) = α, then the vertex set of G can be partitioned into at most α r vertex disjoint monochromatic cycles. In the direction of this conjecture we show that under these conditions the vertex set of G can be partitioned into at most 25(α r ) 2 log(α r ) vertex disjoint monochromatic cycles. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 57–64, 2010