I am trying to design an efficienct algorithm to color a unicyclic graph. I know if a graph does not contain any cycles (it's a tree) then it is 2-colorable. But cycles are either 2 (is even number of vertices) or 3 (is odd number of vertices) colorable. So if there contains just one cycle then the chromatic number of this unicyclic graph should be 3 (if the cycle contains an odd number of vertices).

So enough of that. on to the algorithm.

I would start at a vertex and color it color1. Now I would perform a BSF from the originator. Then each vertex that is adjacent to the originator vertex i would color it color 2, and continue this process of switching from color1 to color 2 unless if one of the vertices has an adjacent vertex that is already colored the same color. That means i found the cycle and will color that vertex color 3. If it had an adajcent vertex that was a different color than what i was going to color it then its an even number cycle and it would be 2-colorable.

So that means, each step of the BFS I would check each vertex adjacent to the vertex selected for that step of the BFS. Therefore $O(|E|)$?

is there a more efficient algorithm to color a unicyclic graph and is my time complexity correct?

  • 6
    $\begingroup$ Just a quick note, if your graph contains only one cycle then you have $|E| \leq |V|$ (why?). $\endgroup$ Dec 16, 2012 at 20:05

1 Answer 1


Yes, your algorithm is correct. The maximum number of edges that a graph can have without forming a cycle is when it is a tree. Lesser number of edges is only when the graph is disconnected. We will assume that the graph is connected, without loss of generality. In such a case, there would be $|V| - 1$ edges in the graph. Any other edge will create one cycle. So, any connected graph with exactly one cycle will have $|V|$ edges.

In such a case, you are right in doing a BFS to color alternatively the nodes alternatively. What you are doing is essentially starting from a root, and all nodes at odd depth have a different color than the root, and all nodes at an even depth have the same color as the root. If you encounter any node which has 2 colored neighbours (parent is always colored, but one of the children is also colored), then you have found a cycle. As you rightly note, if the second vertex is of a different colour than what you planned, it is an even cycle, and you can just go ahead - you will get a 2-coloring. Otherwise, just assign this vertex the third color, and go on with the alternating between two colors for the rest. This gives a 3-coloring.

As for the complexity, you are doing one BFS, checking for colored neighbors while putting them in the queue. Thus, complexity is $O(|V| + |E|)$, as you are visiting every edge and vertex once. However, since $|E| = |V|$, the overall complexity is $O(|V|)$. To color $|V|$ vertices, you need at least $\Omega(|V|)$ time, and so the algorithm is asymptotically optimal (no asymptotically faster algorithm is possible). This algorithm is $\Theta(|V|)$.

  • $\begingroup$ Thanks for confirming my result and giving a much better explanation :) $\endgroup$
    – gprime
    Dec 17, 2012 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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