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:
- Colour all edges in red.
- 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$.
- 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?