2
$\begingroup$

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?enter image description here

$\endgroup$
4
  • 1
    $\begingroup$ Deciding whether a given directed graph can be vertex partitioned into two acyclic subgraphs [is][1] $\text{NP}$-complete. So we know the problem is hard for directed graphs. Why you think it is easier for undirected ones? Did I miss something?! [1]: feb.kuleuven.be/public/u0004371/published%20papers/… $\endgroup$ – Bader Abu Radi Jan 21 at 17:55
  • 1
    $\begingroup$ @BaderAbuRadi The reference you shared is for the vertex coloring. It is not for the edge coloring. :) $\endgroup$ – Inuyasha Yagami Jan 21 at 18:03
  • 1
    $\begingroup$ @Inuyashayagami Oh, I see. Thanks. $\endgroup$ – Bader Abu Radi Jan 21 at 18:05
  • $\begingroup$ I will make an edit to the question. $\endgroup$ – 3nondatur Jan 21 at 18:07
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.