Skip to main content
Share Your Experience: Take the 2024 Developer Survey

New answers tagged

5 votes

Showing the language of all graphs that are both 4-colorable and not 3-colorable is coNP-hard

Let's flip this around using the fact that $L$ is $\text{NP}$-hard iff $\overline{L}$ is $\text{coNP}$-hard. You want to show that $$\text{3-Col} \cup \overline{\text{4-Col}} \text{ is NP-hard}.$$ To ...
Benjamin Kuykendall's user avatar

Top 50 recent answers are included