kcolorability

K-colorability, in graph theory, refers to the property of a graph G = (V,E) that its vertices can be colored with at most k colors so that adjacent vertices receive different colors. A coloring with exactly k colors is called a proper k-coloring. If such a coloring exists, G is said to be k-colorable.

The chromatic number χ(G) is the smallest k for which G is k-colorable. The color classes form a partition of V into independent sets (no edges inside a class). Consequently, χ(G) is at least the size of the largest clique ω(G) and at most Δ(G) + 1, where Δ(G) is the maximum degree; tighter bounds are given by various theorems, such as Brooks’ theorem, which states χ(G) ≤ Δ(G) unless G is a complete graph or an odd cycle.

Examples illustrate the concept. A complete graph K_n requires n colors. An odd cycle, such as C_5, requires three colors, while a bipartite graph (e.g., any even cycle) is 2-colorable. An edgeless graph is 1-colorable.

Computationally, testing k-colorability is easy for k = 1 or 2 (2-colorability is equivalent to checking bipartiteness by a breadth-first search). For fixed k ≥ 3, deciding whether χ(G) ≤ k is NP-complete in general graphs. Related problems include list coloring and preorder coloring variants, which add extra constraints on which colors may be used at each vertex.

In special graph classes, results vary. Every planar graph is 4-colorable (Four Color Theorem), but deciding 3-colorability for planar graphs is NP-complete. Graph coloring has applications in resource allocation, scheduling, and frequency assignment, where colors model distinct resources or time slots.