kcolorable

In graph theory, a graph G is k-colorable if its vertices can be colored with at most k colors so that no two adjacent vertices share a color. A k-coloring is such a proper coloring. The smallest k for which G is k-colorable is called its chromatic number, denoted χ(G). Thus G is k-colorable exactly when χ(G) ≤ k.

Special cases include k = 2. A graph is 2-colorable if and only if it is bipartite. By the four-color theorem, every planar graph is 4-colorable, while some non-planar graphs require more colors. The complete graph on k vertices, K_k, is k-colorable but not (k-1)-colorable, illustrating that χ(K_k) = k.

Computationally, the k-colorability problem asks, given a graph G and an integer k, whether G is k-colorable. It is NP-complete for every fixed k ≥ 3, while for k = 2 the problem is solvable in polynomial time by testing bipartiteness. In practice, algorithms use backtracking, constraint propagation, and heuristics; for small k they are often efficient on many input instances.

k-colorability is studied in various graph classes and in applications such as scheduling, register allocation in compilers, and frequency assignment in telecommunications. It is closely tied to the chromatic number and to broader concepts in graph coloring, including perfect graphs and coloring algorithms.