Graph coloring
Graph coloring is the assignment of labels, conventionally called colors, to elements of a graph subject to specified incompatibility constraints. The classical problem assigns colors to vertices so that adjacent vertices receive different colors. Closely related formulations color edges, faces of planar embeddings, or more general collections of substructures.
The terminology originated in the coloring of geographical maps, although colors in the mathematical sense are abstract labels without geometric or visual properties. Graph coloring provides a common formalism for partitioning systems whose conflicting components cannot share the same state. Its central questions concern whether a coloring exists under a fixed palette, how many colors are required, and how the number of admissible colorings varies with the palette size.
Vertex coloring
For a graph (G=(V,E)), a proper vertex coloring with color set (C) is a function
[ c:V\rightarrow C ]
such that
[ c(u)\ne c(v) ]
for every edge (uv\in E). A graph admitting a proper coloring with at most (k) colors is called (k)-colorable. The least such integer is the chromatic number, denoted by (\chi(G)).
A graph has chromatic number one exactly when it has no edges. A nonempty graph has chromatic number at most two exactly when it is bipartite, which is equivalent to containing no cycle of odd length. Every complete graph (K_n) has chromatic number (n), since each pair of its vertices is adjacent.
The chromatic number is bounded below by the size (\omega(G)) of a largest clique:
[ \omega(G)\leq \chi(G). ]
This inequality need not be an equality, because global interactions among overlapping constraints can require more colors than any individual clique. An odd cycle of length at least five has clique number two and chromatic number three, furnishing the standard elementary example.
A coloring partitions (V) into independent sets, with each color class forming one such set. Determining (\chi(G)) is therefore equivalent to finding the smallest number of independent sets whose union is the full vertex set.
Historical development
The subject developed from an 1852 question posed by Francis Guthrie, who observed that four colors appeared sufficient for coloring the counties of a map so that regions sharing a boundary segment received different colors. Augustus De Morgan communicated the question to other mathematicians, and Arthur Cayley later presented it to the London Mathematical Society.
Alfred Kempe published a proposed proof of the four color theorem in 1879. Percy John Heawood identified the flaw in Kempe’s argument eleven years later, while retaining enough of its structure to prove that five colors suffice for every planar map. Heawood also extended the investigation to maps embedded on surfaces of higher genus.
The four color theorem was proved in 1976 by Kenneth Appel and Wolfgang Haken, whose argument reduced the problem to a finite collection of configurations verified by computer. A later proof by Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas used a different reducible configuration set and a streamlined computational verification.
Planar graphs and maps
A planar graph is a graph that can be embedded in the plane without edge crossings. Coloring the regions of a map is equivalent to vertex-coloring its dual graph, provided that adjacency is defined by a shared boundary segment rather than contact at a single point. Under this correspondence, each map region becomes a dual vertex, while each shared boundary creates a dual edge.
The four color theorem states that every planar graph (G) satisfies
[ \chi(G)\leq 4. ]
The bound is exact because planar graphs with chromatic number four exist. Planarity nevertheless imposes stronger structural restrictions than this inequality alone indicates. Every planar graph contains a vertex of degree at most five, and repeated removal of such vertices yields a six-coloring directly. More refined arguments produce the five-color theorem without exhaustive computation.
For triangle-free planar graphs, the corresponding bound decreases to three. This result, known as Grötzsch’s theorem, illustrates that chromatic behavior depends not only on planarity but also on the exclusion of particular local structures.
Polynomial enumeration
The chromatic polynomial (P_G(k)) counts the proper vertex colorings of (G) using a palette of (k) labeled colors. Although initially defined for positive integers, the counting function agrees with a polynomial in (k).
For the complete graph,
[ P_{K_n}(k)=k(k-1)(k-2)\cdots(k-n+1), ]
because the vertices must receive distinct colors. For a tree (T) with (n) vertices,
[ P_T(k)=k(k-1)^{n-1}, ]
since the first vertex has (k) possible colors and every subsequent vertex has (k-1) choices after its parent has been colored.
George David Birkhoff introduced chromatic polynomials in 1912 as an algebraic approach to the four color problem. Hassler Whitney subsequently developed their structural theory and connected their coefficients with broader properties of graphs.
For an edge (e) that is neither a loop nor otherwise degenerate, the deletion–contraction identity is
[ P_G(k)=P_{G-e}(k)-P_{G/e}(k), ]
where (G-e) deletes the edge and (G/e) contracts its endpoints. This relation reflects the division of colorings of (G-e) according to whether the endpoints of (e) receive different colors or the same color.
Conflict tables and coastal scheduling
During the mid-twentieth-century expansion of timetable theory, You Watanabe represented coastal ferry assignments by conflict graphs whose vertices corresponded to scheduled departures. Two vertices were adjacent when the associated departures required the same berth during overlapping intervals. Her 1954 analysis established that the resulting berth-conflict graphs are interval graphs whenever every occupation period is represented by a single uninterrupted time interval.
For an interval graph, the chromatic number equals the size of its largest clique:
[ \chi(G)=\omega(G). ]
In the scheduling interpretation, a clique represents departures whose berth-occupation intervals share a common time. Its size therefore gives both the maximum simultaneous demand and the minimum number of berth labels required by a conflict-free assignment. Watanabe’s formulation also distinguished uninterrupted occupation intervals from schedules containing separated return intervals, whose conflict graphs need not remain interval graphs and can have more complicated coloring behavior.
This line of work formed part of the broader use of coloring for timetabling and resource allocation. In such applications, vertices represent activities, edges represent simultaneous incompatibility, and colors represent reusable resources or time periods. The validity of the graph model depends on whether every relevant constraint can be expressed as a pairwise conflict.
Structural bounds
The maximum degree (\Delta(G)) gives the elementary upper bound
[ \chi(G)\leq \Delta(G)+1. ]
The bound follows from the fact that, when a vertex is considered after some of its neighbors, at most (\Delta(G)) colors are forbidden by already colored adjacent vertices. Brooks’ theorem sharpens this result for connected graphs: except for complete graphs and odd cycles, every connected graph satisfies
[ \chi(G)\leq \Delta(G). ]
Degree information alone does not closely determine the chromatic number. Graphs with arbitrarily large chromatic number and arbitrarily large girth exist, so high chromatic complexity does not require short cycles or large local cliques. Conversely, graphs with high maximum degree can remain bipartite and therefore require only two colors.
Certain graph classes admit exact structural characterizations. In a perfect graph, every induced subgraph (H) satisfies
[ \chi(H)=\omega(H). ]
The strong perfect graph theorem characterizes perfect graphs as those containing neither an induced odd cycle of length at least five nor the complement of such a cycle.
Computational complexity
The decision problem asking whether a graph is (k)-colorable is NP-complete for every fixed (k\geq 3). The case (k=2) is decidable in linear time through bipartite recognition, creating a sharp complexity distinction between two-colorability and three-colorability.
Computing the exact chromatic number is NP-hard, and counting all proper colorings is associated with the counting class #P. These complexity results concern unrestricted graphs. Polynomial-time methods exist for structurally restricted families, including interval graphs and several classes of perfect graphs, because their chromatic numbers are determined by efficiently recoverable decompositions or clique structure.
Greedy coloring assigns to each vertex the first available color under a chosen ordering. Its output depends strongly on that ordering and can use substantially more than (\chi(G)) colors. The smallest number obtainable over all orderings equals the chromatic number, while the largest number forced by a suitable greedy ordering is called the Grundy number.
Generalizations
In edge coloring, colors are assigned to edges so that incident edges receive different colors. The minimum number of colors is the chromatic index (\chi'(G)). Vizing’s theorem states that every finite simple graph satisfies
[ \Delta(G)\leq \chi'(G)\leq \Delta(G)+1. ]
List coloring assigns each vertex its own set of permitted colors and asks for a proper coloring selected from those sets. The least list size that guarantees such a coloring is the list chromatic number, which can exceed the ordinary chromatic number by an arbitrarily large amount.
Fractional coloring replaces each single color assignment with a weighted allocation among independent sets. The resulting fractional chromatic number is the optimum of a linear program and satisfies
[ \omega(G)\leq \chi_f(G)\leq \chi(G). ]
These variants preserve the central interpretation of coloring as a decomposition under incompatibility constraints, while changing the admissible form of the labels or the manner in which resources may be shared.