Graph coloring: concepts, types, history and applications

Key definitions and types

Basic types of coloring include:

• Vertex coloring — colors assigned to vertices; adjacent vertices must differ.
• Edge coloring — colors assigned to edges so that edges sharing a vertex differ.
• Face or region coloring — colors for regions of a planar drawing (related to map coloring).
• List coloring — each element has its own allowable list of colors; a proper choice is required.

Other notions include the chromatic polynomial, which counts colorings as a function of the number of colors, and fractional or circular colorings that relax the integer color requirement.

History and notable results

The map-coloring motivation goes back to 19th-century questions about coloring countries so neighboring ones differ. The Four Color Theorem, asserting four colors suffice for any planar map, became famous for its long history and for being one of the first major proofs to use computer-aided checking. Many structural results bound chromatic numbers in terms of graph degree or other properties; these include classic theorems that relate maximum degree to colorability except in special cases.

Algorithms and complexity

Deciding the chromatic number or finding an optimal coloring is computationally hard in general (NP-hard). A wide range of algorithms exist: simple greedy heuristics, saturation-based heuristics (e.g., DSATUR), exact exponential backtracking, and integer programming or SAT encodings. Approximating the chromatic number is also difficult, and much research addresses special graph classes where efficient solutions exist.

Applications and examples

Graph coloring models many real problems: scheduling tasks that cannot run simultaneously, assigning frequencies to radio transmitters to avoid interference, register allocation in compilers, and puzzles such as Sudoku (which can be represented as a vertex-coloring instance). Practical instances often use heuristic or domain-specific methods rather than exact computation.

Distinguishing facts

Different coloring problems behave very differently: planar graphs have bounded chromatic numbers, while general graphs can require many colors compared to their size. Variants like list coloring or edge coloring introduce new constraints and theorems. For introductions and formal definitions see standard texts in graph theory or a basic description of a graph.