# Coloring a Unicyclic Graph

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?

• 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

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