Question

What is the condition for proper coloring of a graph?

(a) two vertices having a common edge should not have same color

(b) two vertices having a common edge should always have same color

(c) all vertices should have a different color

(d) all vertices should have same color

The question was asked during an online interview.

I would like to ask this question from Graph Coloring in portion Graph Coloring of Data Structures & Algorithms II

Answer 1

Right answer is (a) two vertices having a common edge should not have same color

Best explanation: The condition for proper coloring of graph is that two vertices which share a common edge should not have the same color. If it uses k colors in the process then it is called k coloring of graph.