Determine if an undirected graph can be colored using only 2 colors

Any hints to how can you determine if an undirected graph can be colored with only 2 colors? How could that be implemen开发者_JAVA百科ted in java?

Do a breadth-first search on the graph. At every even depth, color the nodes one color, say red, and at the odd-depths, you color the nodes blue. Every time you have a non-tree edge (an edge between two nodes you have already visited) verify that the colors are different. If the graph has several connected components, you just repeat the search on each component.

That is same as determining if the graph is bipartite. To do that, you have to check if any odd-length cycle exists in the graph. For that, you do a breadth-first search on the graph. If at any level in the BFS, there is any edge between the nodes of the same level, then the graph is not bipartite, i.e., it can't be colored using only 2 colors. (Assuming the constraint is that the adjacent nodes should be of different colors)