How to avoid monochromatic cycles?
What you are trying to do is find the arboricity of the graph, or equivalently compute the minimum partition into independent sets in the graphic matroid. This problem (for a general matroid) is known as the Matroid partitioning problem, for which polynomial-time algorithms exist.
You can find more details in Harold N. Gabow and Herbert H. Westermann, Forests, frames, and games: Algorithms for matroid sums and applications.