colorability

Colorability is the property of being able to assign colors to the elements of a structure so that specified constraints are satisfied. In graph theory, colorability most often refers to vertex colorings: a k-coloring is an assignment of k colors to the vertices so that adjacent vertices receive different colors. A graph is k-colorable if such an assignment exists, and the chromatic number χ(G) is the smallest k for which the graph is k-colorable.

Key examples illustrate the concept. A graph is 2-colorable if and only if it is bipartite; this fails for odd cycles. A complete graph on n vertices requires n colors. Planar graphs are 4-colorable, as established by the four color theorem; this result relates to map coloring because countries on a map can be modeled by planar graphs, with country colors corresponding to vertex colors of the dual graph.

From a computational perspective, deciding whether a graph is k-colorable is NP-complete for any fixed k ≥ 3, while 2-colorability can be tested in linear time using breadth-first search. For larger instances, exact coloring is challenging, and practical methods include heuristics, integer programming, or fixed-parameter algorithms based on parameters like k or treewidth.

Variants and extensions broaden the notion of colorability. List colorability (choosability) requires each vertex to be colored from a prescribed list of colors. Edge coloring asks for colors of edges so that incident edges differ at a vertex. Fractional and other generalized colorings extend the framework to approximate or probabilistic color assignments.