Family 106Theoretical computer scienceLeanNot yet digested
Hardness of coloring three-colorable graphs
It is NP-hard to color a three-colorable graph using any fixed number c ≥ 3 of colors. More strongly, for every fixed , a deterministic polynomial-time reduction from 3SAT produces simple unweighted graphs that are three-colorable in the satisfiable case and have no independent set of size otherwise, where n is the number of vertices.
Manuscripts in this family · 1
Hardness of finding large independent sets in three-colorable graphs
Sep 24, 2026·Hardness-of-finding-large-independent-sets-in-three-colorable-graphs-September-24-2026.pdfLean
We prove that, for every fixed , it is NP-hard to distinguish three-colorable graphs from graphs in which every independent set has fewer than δ times the number of vertices. Consequently, for every fixed integer c ≥ 3, finding a proper c-coloring of a three-colorable graph is NP-hard.