Graph coloring is a branch of graph theory concerned with assigning labels, traditionally called colors, to vertices, edges, or other parts of a graph subject to specified restrictions. In its standard form, adjacent vertices must receive different colors. The central question is often how many colors are necessary, but coloring theory also investigates how many valid assignments exist, which structural features force particular coloring behavior, and how efficiently a coloring can be found.
Coloring originated in nineteenth-century questions about coloring geographical maps and developed into a major subject connecting combinatorics, topology, probability, and computer science. It also provides a mathematical language for assigning scarce resources to mutually incompatible activities. Although checking a proposed coloring is straightforward, finding one that uses the fewest colors can be computationally difficult. This contrast between a simple local rule and complex global consequences is a defining feature of the subject.
Vertex coloring and its basic invariants
Unless otherwise specified, coloring theory considers a finite, undirected, simple graph , where is its vertex set and its edge set. A proper -coloring is a function
such that whenever . The colors are merely labels: their visual appearance and numerical order have no significance. A coloring need not use every available label. The least number of colors permitting a proper coloring is the chromatic number, written . Under the usual convention, the graph with no vertices has chromatic number , while a nonempty graph with no edges has chromatic number .
Each set of vertices receiving one color is an independent set, meaning that no two vertices in it are adjacent. A coloring therefore gives a partition of the vertex set into independent sets. This alternative formulation turns coloring into a covering or partitioning problem and connects it directly to optimization. In the complementary graph, where two distinct vertices are adjacent exactly when they were nonadjacent in the original graph, those same color classes become complete subgraphs.
Basic graph families illustrate different sources of coloring constraints. The complete graph , in which every pair of distinct vertices is adjacent, requires colors. A path containing at least one edge needs two. A cycle needs two colors when its length is even and three when its length is odd. A graph is a bipartite graph precisely when its vertices can be separated into two independent sets, equivalently when it has no odd cycle. A graph containing an edge is consequently bipartite exactly when its chromatic number is .
Several qualifications matter when extending the definition. Parallel edges impose no additional restrictions on vertex coloring, whereas a loop makes a proper coloring impossible because it would require a vertex to differ from itself. For a disconnected graph, the chromatic number is the maximum chromatic number of its connected components: the same palette can be reused in different components. A subgraph can never have larger chromatic number than its parent graph. These elementary observations support many proofs based on deleting vertices or edges and then extending a coloring. They also explain why coloring questions usually focus on loopless graphs and why connected graphs provide the essential cases for many structural theorems.
Bounds, greedy methods, and critical graphs
Two elementary bounds organize much of vertex-coloring theory. Let be the largest number of vertices in a clique, and let be the largest size of an independent set. Since all vertices of a clique require distinct colors, and every color class has at most vertices,
These bounds measure different obstructions: a single dense subgraph can force many colors, but so can the absence of large independent sets throughout the graph. Neither bound alone characterizes the chromatic number.
The simplest general upper bound comes from a greedy algorithm. Arrange the vertices in an order and color them successively, assigning each the smallest color not already used on a colored neighbor. If the maximum vertex degree is , at most colors are forbidden at any step, so
The result depends strongly on the ordering. A crown graph, obtained from by deleting a perfect matching, is bipartite, yet a suitably interleaved ordering of its matched pairs makes greedy coloring use colors. Thus a poor ordering can produce arbitrarily bad results even on a simple two-colorable family.
A more structural guarantee uses degeneracy. A graph is -degenerate if every nonempty subgraph has a vertex of degree at most . Repeatedly removing such a vertex and then coloring in reverse removal order proves that every -degenerate graph is -colorable. Trees are -degenerate, and every simple planar graph is -degenerate. Brooks’s theorem, proved by R. Leonard Brooks in 1941, sharpens the maximum-degree bound: a connected graph has unless it is a complete graph or an odd cycle. Its exceptions show that degree constraints interact with the arrangement of edges, not merely their number.
Minimal obstructions are studied through critical graphs. A graph is vertex-critical if deleting any vertex reduces its chromatic number. If such a graph has chromatic number , every vertex has degree at least : otherwise a -coloring of the remaining graph could be extended to the deleted vertex. Consequently, an -vertex, vertex-critical -chromatic graph has at least edges. Criticality is useful because a hypothetical counterexample to a coloring theorem can often be reduced to a critical one, where minimum-degree conditions and restrictions on local configurations become available.
Map coloring and graphs on surfaces
The historical starting point of coloring theory was the question of how many colors suffice for a map when regions sharing a boundary segment must differ. Francis Guthrie raised the four-color question in 1852, and Augustus De Morgan helped bring it to wider mathematical attention. The appropriate graph has one vertex for each region and an edge for each adjacency. For ordinary finite maps with suitably connected regions, this leads to a planar graph: a graph drawable in the plane without crossings between edge interiors. Regions meeting only at a point are not regarded as adjacent.
The four-color theorem states that every loopless planar graph has a proper vertex coloring with at most four colors. Alfred Kempe published a purported proof in 1879, but Percy Heawood identified a flaw in 1890. Kempe’s recoloring method nevertheless remained important. Given a proper coloring, consider a connected component of the subgraph induced by two colors. Interchanging those two colors throughout the component preserves properness. Such components, called Kempe chains, can sometimes free a color at a chosen vertex and remain standard tools in coloring proofs.
Planarity already gives an elementary six-color theorem. Euler’s formula implies that a simple planar graph with vertices has at most edges, so some vertex has degree at most five. Repeated deletion and greedy extension then use at most six colors. Heawood’s five-color theorem improves this by applying a Kempe-chain argument when a deleted vertex has five differently colored neighbors. Reaching four colors requires much more elaborate reasoning. Kenneth Appel and Wolfgang Haken announced the first proof in 1976, using extensive computer checking of reducible configurations and a discharging argument. A later proof by Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas simplified the computational framework. Georges Gonthier completed a machine-checked formalization in 2005, making the theorem an important case in formal verification.
Other surfaces permit greater chromatic numbers. For the closed orientable surface with handles, the maximum chromatic number among embeddable simple graphs is
Thus seven colors are sometimes necessary and always sufficient on the torus. The sharp general result belongs to the map-color theorem established through work culminating with Gerhard Ringel and J. W. T. Youngs in 1968. The sphere has maximum four. Nonorientable surfaces have a related formula, with the Klein bottle an exceptional case requiring at most six rather than the formula’s seven. These results connect coloring to the topology of embeddings rather than to visual complexity alone.
Perfect graphs, forbidden structures, and minors
Clique size supplies a necessary lower bound for coloring, but the gap between and can be arbitrarily large. Structural graph theory asks which restrictions keep that gap under control. A perfect graph is a graph for which
for every induced subgraph , including the graph itself. An induced subgraph retains all edges between its selected vertices. Requiring equality throughout this hereditary family is much stronger than requiring it only for the original graph.
Important perfect graph classes admit especially transparent coloring methods. In an interval graph, vertices represent intervals on a line and adjacency means intersection. Its chromatic number equals the greatest number of intervals covering a common point. A chordal graph has no induced cycle of length at least four. Such graphs possess a perfect elimination ordering, in which the later neighbors of each vertex form a clique; greedy coloring in the reverse order is optimal. Bipartite graphs are also perfect. These examples show how geometry or elimination structure can make the general coloring problem tractable.
Claude Berge introduced perfect graphs in the early 1960s and proposed their central structural characterization. The strong perfect graph theorem, proved by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas and published in 2006, states that a graph is perfect exactly when it contains neither an induced odd cycle of length at least five nor the complement of such a cycle. These forbidden graphs are called odd holes and odd antiholes. The theorem explains the obstructions structurally; separate optimization methods establish that maximum clique and minimum coloring can be found in polynomial time for perfect graphs.
A different approach uses a graph minor, obtained by deleting vertices, deleting edges, and contracting edges. Hadwiger’s conjecture, proposed in 1943, states that every graph with chromatic number at least contains as a minor. It would relate a coloring requirement to the presence of a complete graph assembled from disjoint connected vertex sets with edges between every pair. The conjecture is known for , but remains unresolved in general. Its case is equivalent to the four-color theorem. Although taking a subgraph cannot increase chromatic number, taking a minor can: contracting an edge of a four-cycle produces a triangle. Thus minor theory does not follow from ordinary coloring monotonicity, and the conjecture expresses a substantially deeper connection between coloring and connectivity.
Counting colorings and algebraic methods
The chromatic number records only whether a sufficiently small palette works. The chromatic polynomial records how many proper assignments exist. For a finite graph , let be the number of proper colorings using available, distinguishable colors, where is a nonnegative integer. George David Birkhoff introduced this approach in 1912 while studying the four-color problem. Despite being defined through counting, agrees with a polynomial in , and its first positive integer argument with nonzero value is .
The fundamental identity is deletion–contraction. If is an edge joining distinct vertices, then
A proper coloring of either gives the endpoints of different colors, in which case it colors , or gives them the same color, in which case it corresponds to a coloring of the contracted graph . Repeated application reduces the problem to edgeless graphs, for which . This proves polynomiality and gives an exact recursive algorithm, although a direct implementation can require exponential time.
For a tree on vertices,
because a root has choices and each successive vertex must only avoid its parent’s color. For the cycle ,
For , the polynomial is . More generally, an -vertex simple graph with edges has a monic chromatic polynomial of degree , whose coefficient of is . The polynomial nevertheless does not determine the graph: all trees with the same number of vertices have the same chromatic polynomial.
Algebraic evaluations also encode objects other than colorings. Richard Stanley proved that counts acyclic orientations, assignments of directions to edges that produce a directed acyclic graph. The chromatic polynomial is a specialization of the Tutte polynomial, a two-variable invariant connecting colorings, flows, spanning trees, and network properties. Another connection comes from statistical physics: proper -colorings are the zero-energy configurations of the antiferromagnetic -state Potts model, where adjacent equal states are penalized. Thus counting colorings links discrete enumeration to partition functions and phase behavior. Complex roots of chromatic polynomials can be studied algebraically even though noninteger or complex arguments no longer count ordinary color assignments directly.
Edge coloring and total coloring
In edge coloring, colors are assigned to edges so that any two edges sharing an endpoint receive different colors. Each color class is therefore a matching, a set of pairwise nonincident edges. The minimum number of colors is the chromatic index, denoted . Since all edges incident with a maximum-degree vertex need distinct colors,
Edge coloring can be expressed as vertex coloring of a line graph: each original edge becomes a vertex, and two new vertices are adjacent when their original edges share an endpoint. Line graphs have special structure, however, so edge-coloring results are often stronger than those available for arbitrary vertex coloring.
Vizing’s theorem, established in 1964, states that every finite simple graph satisfies
Graphs attaining the lower value are called class 1, and those needing the upper value are class 2. An even cycle is class 1, while an odd cycle is class 2. For complete graphs, needs edge colors and needs . The latter lower bound follows because each matching has at most edges, while the graph has edges.
Bipartite graphs have an exact theorem: König’s line-coloring theorem states that every bipartite multigraph has chromatic index equal to its maximum degree. One proof augments the graph to a regular bipartite multigraph and repeatedly removes a perfect matching. Each removed matching becomes a color class. Allowing parallel edges changes general bounds substantially: three vertices with parallel edges between each pair have maximum degree , but all edges are pairwise incident and need distinct colors. Shannon’s bound guarantees at most colors for a loopless multigraph, showing that this example is extremal.
Total coloring assigns colors to both vertices and edges. Adjacent vertices must differ, incident edges must differ, and an edge must differ from both its endpoints. The elements consisting of a vertex and all its incident edges immediately require at least colors. The total coloring conjecture asserts that always suffice for a simple graph; it remains open in full generality. These variants model different compatibility rules. In a round-robin tournament, for example, teams are vertices and games are edges. An edge color represents a round in which no team plays twice. For an even number of teams, the edge coloring of a complete graph gives a schedule with exactly one fewer round than teams; an odd number requires an additional round and gives each team one bye.
Lists, fractional colorings, and other variants
Ordinary coloring assumes that every vertex has access to the same palette. In list coloring, each vertex has a prescribed set of allowed colors, and a proper coloring must satisfy . A graph is -choosable if every assignment of lists of size at least permits such a coloring. Its list chromatic number, or choice number, is the least such . Necessarily,
The upper bound follows from the greedy argument, since each already colored neighbor forbids at most one listed color.
List coloring captures nonuniform availability and differs sharply from ordinary coloring. Bipartite graphs always need at most two ordinary colors, but their choice numbers are unbounded. For planar graphs, Carsten Thomassen proved in 1994 that lists of size five always suffice; lists of size four do not suffice for every planar graph. For edge coloring, lists are assigned to edges. The list edge-coloring conjecture asserts that the list chromatic index always equals the ordinary chromatic index. Fred Galvin proved this equality for bipartite multigraphs in 1995, extending König’s theorem to arbitrary edge lists.
Fractional coloring replaces an indivisible palette by divisible weights. Let be the family of independent sets of . Assign a nonnegative weight to each , requiring each vertex to receive total coverage at least one:
This is a linear program, though it may have exponentially many variables. It gives . On the five-cycle, assigning weight to each of its five independent pairs yields , whereas . Equivalently, fractional coloring describes the limiting efficiency of assigning several colors to each vertex while adjacent vertices receive disjoint sets.
Other variants change what counts as a conflict. Distance-two coloring requires vertices at graph distance one or two to differ; it is ordinary coloring of the graph square. Acyclic coloring requires every subgraph induced by two color classes to be a forest. Equitable coloring requires the sizes of color classes to differ by at most one, incorporating load balance as well as compatibility. Precoloring extension asks whether a given partial coloring can be completed. A graph homomorphism provides a unifying perspective: an ordinary -coloring is a homomorphism to , while other target graphs encode different allowed relationships between labels. These definitions address distinct mathematical constraints and generally have different optimal values.
Computational complexity and coloring algorithms
For a given coloring, checking properness requires inspecting each edge, so verification is straightforward. Finding an optimal coloring is another matter. For each fixed , deciding whether an arbitrary graph is -colorable is NP-complete. This places coloring among the central problems of computational complexity: a proposed solution can be verified efficiently, but no polynomial-time algorithm is known for all inputs. Two-colorability is an important exception. Breadth-first or depth-first search assigns alternating colors along edges and either produces a bipartition or detects an odd cycle, in time proportional to the number of vertices and edges.
Exact algorithms commonly use backtracking and branch-and-bound. A partial coloring is extended one vertex at a time, with branches abandoned when a conflict occurs or when a lower bound rules out improvement. Daniel Brélaz’s DSATUR method, introduced in 1979, selects a vertex with maximum saturation degree, meaning the number of distinct colors already present among its colored neighbors. As a greedy procedure it is a heuristic; embedded in complete branching and bounding, it supports an exact algorithm. Its selection rule tends to handle constrained vertices early, but it does not eliminate exponential worst-case behavior.
Coloring also has useful mathematical-programming formulations. With a fixed palette, binary variables indicate whether vertex receives color . The constraints are
Additional binary variables can record which colors are used, producing an integer program whose objective minimizes their number. An alternative formulation selects independent sets as color classes. That approach has exponentially many potential variables and often uses column generation, introducing promising independent sets as needed. Boolean satisfiability encodings express the same assignment and incompatibility conditions through logical clauses.
Polynomial-time algorithms exist on many restricted graph classes, including bipartite, chordal, interval, and perfect graphs, although the methods differ substantially. Dynamic programming also works efficiently when a graph is supplied with a tree decomposition of bounded width. For unrestricted graphs, practical methods combine structural preprocessing, greedy upper bounds, clique-based lower bounds, local search, and simulated annealing or related metaheuristics. An explicit coloring certifies an upper bound on , not optimality. Establishing optimality requires a matching lower bound or a complete argument that fewer colors are impossible. This distinction is essential when reporting computational results on large instances.
Resource allocation and scientific applications
The standard application of vertex coloring begins with a conflict graph. Each vertex represents an activity, object, or request, and an edge records a pair that cannot share a resource. Colors represent interchangeable resources. This model appears throughout operations research, but its accuracy depends on the conflict relation and on the assumption that all restrictions are pairwise. Constraints involving capacities, groups of three or more activities, unequal durations, or unequal resource capabilities require extensions or additional optimization machinery.
In examination timetabling, vertices can represent examinations, with an edge between two examinations whenever at least one student must attend both. A proper coloring assigns time slots without simultaneous conflicts. The chromatic number gives the minimum number of slots for this simplified problem. Actual timetables may also constrain room capacity, instructor availability, examination length, and the spacing of each student’s examinations. Equitable coloring can encourage balanced slot sizes, but balancing numbers of examinations does not necessarily balance student attendance or room demand. These distinctions separate the graph-theoretic core from the full scheduling problem.
Register allocation in a compiler provides another influential example. Program values are represented by vertices of an interference graph; two values are adjacent when they must be kept simultaneously and therefore cannot occupy the same machine register. A coloring with colors assigns values to registers. When such a coloring is unavailable, some values may be spilled to memory, and transformations such as splitting live ranges can change the graph. George Chaitin and collaborators developed an influential graph-coloring approach at IBM around 1981. Real architectures add restrictions such as register classes, reserved registers, and instructions requiring particular locations, making list coloring and preassignment natural refinements of the basic model.
Communication systems use colors for channels or transmission periods. An edge can represent unacceptable interference if two transmitters use the same channel. When nearby frequencies also interfere, labels acquire numerical separation requirements, and the problem is no longer ordinary coloring. Edge coloring instead models transmissions that share an endpoint and cannot occur simultaneously. Fractional coloring can represent long-run time sharing among compatible sets of transmitters. In scientific computing, coloring a graph derived from the sparsity pattern of a matrix can group columns whose nonzero entries do not overlap in the same row. Such groups allow simultaneous perturbations when estimating a sparse Jacobian matrix, reducing the number of function evaluations. Here the colors represent compatible computational experiments rather than physical resources, while the same independent-set principle determines which operations can be combined.
Probabilistic, spectral, and infinite coloring
Dense local structure is not the only source of high chromatic number. In 1955, Jan Mycielski gave a construction that raises the chromatic number by one while preserving the absence of triangles. Starting with a single edge and iterating the construction produces triangle-free graphs of arbitrarily large chromatic number. Thus the maximum clique size cannot bound the chromatic number for all graphs. Paul Erdős proved a stronger existence theorem in 1959: for any prescribed integers and , there is a graph with girth greater than and chromatic number greater than . Even graphs with no short cycles can therefore require many colors.
Erdős’s argument exemplifies the probabilistic method. A suitable random graph is likely to have no very large independent set, which forces a large chromatic number. At the same time, the expected number of short cycles can be controlled. Deleting a limited number of vertices destroys those cycles while leaving enough vertices to preserve a high coloring requirement. Random graph theory also gives quantitative behavior in typical dense graphs. For fixed edge probability with , the random graph satisfies, with probability tending to one,
The scale reflects the fact that its largest independent sets have size roughly .
Spectral methods provide lower bounds from eigenvalues. For a graph with at least one edge, let and be the largest and smallest eigenvalues of its adjacency matrix. Hoffman’s bound gives
For a -regular graph, . This makes spectral information useful when the graph is too large or symmetric for direct coloring analysis. The bound is exact for complete graphs and for regular bipartite graphs, but it can be weaker than other available bounds on different families.
Infinite graphs introduce a distinct compactness phenomenon. The de Bruijn–Erdős theorem, proved in 1951, states that for a fixed finite , an infinite graph is -colorable if every finite subgraph is -colorable. In ordinary set-theoretic foundations this follows from a compactness argument, closely related to the compactness theorem of logic. It transfers finite uniform bounds to infinite settings without asserting that an infinite coloring can be constructed by a finite algorithm. Coloring also extends into geometry: in the unit-distance graph of the Euclidean plane, points are adjacent when their distance is exactly one. Its chromatic number is known to lie between five and seven, the lower bound having been raised from four by Aubrey de Grey in 2018. This problem combines finite obstruction graphs, geometric constructions, and infinite color assignments within a single coloring question.