How to avoid monochromatic cycles?

Question

I am working on the following exercise:

Consider a simple and connected undirected graph $G(V,E)$. Show that one can colour the edges of $G$ in polynomial time and with as few colours as possible such that there is no monochromatic cycle in said colouring of $G$.

EDIT 1: OK, my approach turned out to be false. I will leave it here for the sake of completeness. Now I have no idea how to solve this exercise. I guess the following theorem might be helpful:

Theorem: For any undirected simple graph $G(V,E)$ we can decide whether the edge chromatic number is less than $3$ and if yes we can find this optimal colouring in polynomial time.

EDIT 2: I have reread my lecture notes. This exercise is probably meant to be solved with tools from matroid theory. I just do not see how.

---

My WRONG approach:

I think that 2 colours should be sufficient. (Remember that this is not the classical edge colouring problem, we just want to avoid monochromatic cycles.) My first idea is to formulate a simple greedy algorithm:

1. Colour all edges in red.
2. Check the graph for cycles. If there is a cycle delete one edge of the cycle from the graph. Repeat this step until there are no more cycles in $G$.
3. Colour the deleted edges in blue.

However, the problem with this approach is that the blue edges may form a cylce as the example below shows. While the example below can easily be fixed by recolouring two edges I am not sure if this fix works in general. Could you please give me a hint?

Answer 1

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.