Cheap and Secure Web Hosting Provider : See Now

[Answers] Is it NP-complete to decide if chromatic and clique numbers agree?

, , No Comments
Problem Detail: 

It is known that finding chromatic number $\chi(G)$ and clique number $\omega(G)$ are both NP-complete problems.

Is the problem

Given graph $G$, is $\omega(G)=\chi(G)$?

NP-complete as well?

Side question: is there a name for such graphs?

Asked By : AJ.

Answered By : Yuval Filmus

Your problem is NP-complete. See for example this question on ResearchGate.

Your problem is in NP because to show that $\omega(G) = \chi(G)$ it is sufficient to exhibit a $k$-clique and a $k$-coloring, for some $k$.

Your problem is NP-hard by reduction from 3COL. Given a graph $G$, first check whether it contains a $K_4$, and if so output some trivial No instance (say a $5$-cycle). Otherwise, add a triangle to your graph. The original graph is 3-colorable iff the new one satisfies your condition.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback