Graph Coloring

Graph coloring assigns labels, or colors, to graph elements so that adjacent elements differ, and studies the minimum number of colors required.

Definition

A proper coloring of a graph is an assignment of colors to its vertices so that no two adjacent vertices share a color; the chromatic number is the least number of colors for which such an assignment exists.

Scope

This topic treats proper vertex coloring and the chromatic number, edge coloring and the chromatic index, the chromatic polynomial that counts colorings, and landmark results including Brooks' theorem, Vizing's theorem, and the Four Color Theorem for planar graphs. It links coloring to independence, cliques, and the broader theory of graph parameters.

Core questions

• What is the fewest number of colors needed to properly color a given graph?
• How many proper colorings with a given palette does a graph admit?
• Which graphs can be colored with few colors, and what obstructions force many?
• How do edge colorings and list colorings extend the basic notion?

Key concepts

• Proper vertex coloring
• Chromatic number
• Chromatic polynomial
• Edge coloring and chromatic index
• Brooks' theorem
• Four Color Theorem

Key theories

Four Color Theorem

Every planar graph can be properly colored with at most four colors, a statement open for over a century and first proved by Appel and Haken in 1976 using extensive computer-assisted case analysis.

Vizing's theorem

The edges of any simple graph can be properly colored with either the maximum degree or one more than the maximum degree colors, splitting all graphs into two narrow classes.

Clinical relevance

Coloring models conflict-free resource allocation: scheduling without clashes, register allocation in compilers, frequency assignment in wireless networks, and Sudoku-style constraint problems all reduce to graph coloring.

History

The Four Color Conjecture, posed in 1852, drove much of coloring theory; its 1976 computer-assisted proof by Appel and Haken was an early landmark in computer-assisted mathematics and sparked debate about the nature of proof.

Debates

Status of computer-assisted proofs

The Four Color Theorem's reliance on machine-checked cases raised the question of whether a proof too long for a human to verify by hand should count as a genuine mathematical proof.

Key figures

• Kenneth Appel
• Wolfgang Haken
• Vadim Vizing

Seminal works

• diestel2017

Frequently asked questions

What is the chromatic number of a graph?

It is the smallest number of colors needed so that adjacent vertices always receive different colors; for example, an odd cycle has chromatic number three.

Does the Four Color Theorem apply to all maps?

It applies to maps drawn on the plane or sphere where regions are connected; maps on surfaces such as the torus can require more colors.