Microsoft Interview Question: Graph Coloring problem: given a connected graph, color each node in the graph such that no two adjacent nodes have the same color.

Notifications

Microsoft

Graph Coloring problem: given a connected graph, color each node in the graph such that no two adjacent nodes have the same color.

Anonymous

Nov 7, 2011

@dopey this only works if the graph is bipartite. it does not work in the general case.

Anonymous

Oct 3, 2011

Do a BFS with two colors. Alternate the colors at each round.