Reference no: EM131944972

A 2-coloring of an undirected graph with n vertices and m edges is the assignment of one of two colors (say, black or white) to each vertex of the graph so that no two adjacent nodes have the same color. So, if there is an edge (u; v) in the graph, either node u is black and v is white or vice versa. Give an O(n+m) time algorithm to a 2-color a graph or determine that no such coloring exists, and justify the running time. For this problem, you are not allowed to assume the existence of any "black-box" algorithms. You can use a pseudo-code instead of a full detailed algorithm.