patternMinor
Is it NP-complete to decide if chromatic and clique numbers agree?
Viewed 0 times
numberscliqueagreechromaticcompletedecideand
Problem
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?
Is the problem
Given graph $G$, is $\omega(G)=\chi(G)$?
NP-complete as well?
Side question: is there a name for such graphs?
Solution
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.
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.
Context
StackExchange Computer Science Q#65035, answer score: 4
Revisions (0)
No revisions yet.