Question

What is vertex coloring of a graph?

(a) A condition where any two vertices having a common edge should not have same color

(b) A condition where any two vertices having a common edge should always have same color

(c) A condition where all vertices should have a different color

(d) A condition where all vertices should have same color

This question was posed to me in an international level competition.

Question is taken from Graph Coloring in portion Graph Coloring of Data Structures & Algorithms II

Answer 1

The correct answer is (a) A condition where any two vertices having a common edge should not have same color

Easiest explanation - The condition for vertex coloring of a 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.