Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
6  
Just a quick note, if your graph contains only one cycle then you have $|E| \leq |V|$ (why?). –  Yuval Filmus Dec 16 '12 at 20:05

1 Answer 1

up vote 6 down vote accepted

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|)$.

share|improve this answer
    
Thanks for confirming my result and giving a much better explanation :) –  gprime Dec 17 '12 at 18:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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