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?