rcoloring

r-coloring is a concept in graph theory describing a way to assign colors to the vertices of a graph using at most r colors so that no two adjacent vertices share the same color. The smallest r for which such a coloring exists is the graph’s chromatic number, denoted χ(G). An r-coloring is thus a proper coloring with r colors, and a graph is r-colorable if χ(G) ≤ r.

In basic terms, many graphs can be colored with a small number of colors, but the exact number depends on the structure of the graph. A simple observation is that a greedy coloring using vertex order guarantees an (Δ+1)-coloring, where Δ is the maximum degree. Brooks’ theorem sharpens this bound by stating χ(G) ≤ Δ unless the graph is complete or an odd cycle. Consequently, complete graphs Kn require n colors, while odd cycles require 3 colors. Planar graphs are famously 4-colorable, by the Four Color Theorem.

Complexity and computation: For fixed r ≥ 3, deciding whether a given graph is r-colorable is NP-complete. By contrast, 2-colorability, which corresponds to bipartiteness, can be tested in polynomial time with a breadth-first search. In general, computing the exact chromatic number χ(G) is NP-hard, and no efficient algorithm is known for all graphs.

Algorithms and variants: Practical coloring uses heuristics and exact methods. Algorithms such as greedy coloring and DSATUR (saturation-degree ordering) are common. Variants include list coloring (each vertex has an allowed color set), equitable coloring (balanced color class sizes), online coloring (colors are assigned in a sequence without knowledge of the future), and fractional coloring (a relaxation allowing weighted colorings).

Applications: Graph coloring models resource allocation problems in scheduling, register allocation in compilers, map coloring, and frequency assignment in communications.