Question

Calculating the chromatic number of a graph is a

(a) P problem

(b) NP hard problem

(c) NP complete problem

(d) cannot be identified as any of the given problem types

This question was addressed to me in an online quiz.

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

Answer 1

The correct answer is (c) NP complete problem

The explanation is: Chromatic number of an arbitrary graph cannot be determined by using any convenient method. So calculating the chromatic number of a graph is an NP complete problem.