Graph K-Colorability

Input

Graph $G = (V, E)$, positive integer $K \leq |V|$.

Question

Is $G$ $K$-colorable, i.e. does there exist a function $f: V \rightarrow \{1, 2, \dots, K\}$ such that $f(u) \neq f(v)$ whenever $\{u, v\} \in E$?

Classes

• NP-complete

Comments

Solvable in polynomial time for $K = 2$, but remains NP-complete for all fixed $K \geq 3$ and, for $K = 3$, for planar graphs having no vertex degree exceeding 4 (Garey et al., 1976). Also remains NP-complete for $K = 3$ if $G$ is an intersection graph for straight line segments in the plane (Ehrlich et al., 1976). For arbitrary $K$, the problem is NP-complete for circle graphs and circular arc graphs (even given their representation as families of arcs), although for circular arc graphs the problem is solvable in polynomial time for any fixed $K$ (given their representation). The general problem can be solved in polynomial time for comparability graphs (Even et al., 1972), for chordal graphs (Gavril, 1972), for $(3, 1)$ graphs (Walsh & Burkhard, 1977), and for graphs having no vertex degree exceeding 3 (Brooks, 1941).

Proofs

NP-complete

Transformation from 3-Satisfiability (Karp, 1972).

Reducible from

• 3-Satisfiability

Reducible to

• Partition into Cliques

References

• Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237–267. https://doi.org/10.1016/0304-3975(76)90059-1
• Ehrlich, G., Even, S., & Tarjan, R. E. (1976). Intersection graphs of curves in the plane. Journal of Combinatorial Theory, Series B, 21(1), 8–20. https://doi.org/10.1016/0095-8956(76)90022-8
• Even, S., Pnueli, A., & Lempel, A. (1972). Permutation Graphs and Transitive Graphs. Journal of the ACM, 19(3), 400–410. https://doi.org/10.1145/321707.321710
• Gavril, F. (1972). Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. SIAM Journal on Computing, 1(2), 180–187. https://doi.org/10.1137/0201013
• Walsh, A. M., & Burkhard, W. A. (1977). Efficient algorithms for (3, 1) graphs. Information Sciences, 13(1), 1–10. https://doi.org/10.1016/0020-0255(77)90009-3
• Brooks, R. L. (1941). On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37(2), 194–197. https://doi.org/10.1017/s030500410002168x
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9