colorable

Colorable is an adjective used to describe an object or structure for which a coloring exists that meets specified rules. In mathematics and related fields, a problem is called colorable when there is a way to assign colors to its elements so that the constraints of the coloring are satisfied.

In graph theory, the phrase is most often encountered with vertex coloring. A graph is k-colorable if its vertices can be colored with at most k colors so that adjacent vertices receive different colors. The chromatic number χ(G) is the smallest k for which the graph is k-colorable. Examples include: bipartite graphs, which are 2-colorable; a triangle, which requires 3 colors; and a complete graph on n vertices, which requires n colors. The Four Color Theorem states that every planar graph is 4-colorable.

Algorithmic and computational considerations are central to colorability. Greedy coloring can produce a coloring using at most Δ+1 colors, where Δ is the maximum degree, but this may not be optimal. More advanced methods include DSATUR and backtracking search. Deciding whether a given graph is k-colorable is NP-complete for k ≥ 3, making exact solutions intractable for large instances in general. Some restricted classes of graphs and specific coloring variants admit efficient algorithms.

Beyond graphs, colorability appears in map coloring, scheduling, and resource allocation, as well as in edge coloring (where colors distinguish incident edges) and list coloring (where each vertex has its own allowed color set). In each context, colorability concerns whether a suitable coloring exists under the problem’s rules.