Chromatic polynomial
The chromatic polynomial of a graph G is a monic polynomial P_G(k) of degree equal to the number of vertices in G, which counts the number of proper vertex colorings of G using exactly k colors, where adjacent vertices receive distinct colors.[1] This polynomial was first introduced by George D. Birkhoff in 1912, who defined it in the context of map coloring to seek an algebraic approach to the four-color theorem for planar graphs.[2] Key properties of the chromatic polynomial include its multiplicativity over disjoint unions of graphs, meaning P_{G \cup H}(k) = P_G(k) \cdot P_H(k) for graphs G and H with no edges between them, and the deletion-contraction recurrence: for a non-loop edge e in G, P_G(k) = P_{G-e}(k) - P_{G/e}(k), where G-e is G with e removed and G/e is G with the endpoints of e identified.[1] These properties facilitate recursive computation, though evaluating the polynomial exactly is computationally intensive for large graphs, with known algorithms running in exponential time.[3] The value P_G(k) is zero for k < \chi(G), where \chi(G) is the chromatic number (the smallest integer k such that P_G(k) > 0), providing a direct link to graph coloring complexity.[4] Notable examples include the empty graph on n vertices, with P_G(k) = k^n; the complete graph K_n, with P_G(k) = k(k-1)\cdots(k-n+1); and trees on n vertices, with P_G(k) = k(k-1)^{n-1}.[1] The chromatic polynomial also connects to broader algebraic graph theory, such as the Tutte polynomial via the relation P_G(k) = (-1)^{|V|-c} k^c T_G(1-k, 0), where c is the number of connected components, enabling studies in matroid theory and statistical mechanics models like the Potts model.[5] Despite extensive research, open questions persist, including efficient computation methods and characterizations of which polynomials arise as chromatic polynomials of some graph.[1]Definition
Formal definition
The chromatic polynomial of a graph G, denoted P_G(k), counts the number of proper vertex colorings of G using at most k distinguishable colors, such that no two adjacent vertices receive the same color. The chromatic polynomial was introduced by George D. Birkhoff in 1912. Further developments, including the deletion-contraction recurrence, were made by Hassler Whitney in 1932.[6][7][4] A proper coloring assigns colors to the vertices of G from a set of k available colors in such a way that adjacent vertices must differ in color.[4] The function P_G(k) is a monic polynomial in the variable k of degree n, where n is the number of vertices in G, and it has integer coefficients that alternate in sign.[4][5] For any graph G with at least one vertex, P_G(0) = 0, which holds in particular for connected graphs containing edges; in general, the value of P_G(k) factors as the product over the chromatic polynomials of its connected components, thereby relating it to the number of such components.[4][6] For the introductory example of an edgeless graph on n vertices, P_G(k) = k^n, since there are no adjacency constraints and each vertex may be colored freely.[4]Deletion-contraction recurrence
The deletion-contraction recurrence is a cornerstone for computing the chromatic polynomial P_G(k) of a graph G, providing a recursive relation based on edge operations. For any non-loop edge e in G, the formula states: P_G(k) = P_{G - e}(k) - P_{G / e}(k), where G - e denotes the deletion of e (the graph G with e removed, preserving all other edges and vertices), and G / e denotes the contraction of e. This recurrence, introduced by Hassler Whitney, allows the polynomial to be expressed in terms of simpler subgraphs.[8] Contraction of an edge e = \{u, v\} merges vertices u and v into a single new vertex w, with all edges originally incident to u or v now incident to w; any self-loops formed in this process are removed, as loops prevent proper colorings. Deletion simply removes e without altering vertices or other edges. These operations preserve the structure relevant to coloring counts while reducing the graph's complexity.[8] The proof relies on an inclusion-exclusion principle applied to proper k-colorings. The quantity P_{G - e}(k) counts all proper colorings of G - e, which include cases where the endpoints of e receive the same color or different colors. Proper colorings of G correspond precisely to those of G - e where the endpoints have different colors, since e forbids the same color. The colorings of G - e where the endpoints share a color are in bijection with the proper colorings of G / e, as contraction enforces the same color on the identified vertices. Subtracting P_{G / e}(k) thus isolates the valid colorings for G.[8] Base cases anchor the recurrence. For a graph with a single vertex (edgeless with one vertex), P_G(k) = k, as there is one way to color it with each of k colors. A graph containing a loop has P_G(k) = 0 for all k, since no proper coloring exists. For the graph consisting of two vertices connected by a single edge, P_G(k) = k(k-1), accounting for choices of distinct colors for the endpoints. These cases handle terminal reductions in the recursion.[9] The recurrence defines a unique polynomial, as iterative application to any edge sequence reduces G to disjoint unions of isolated vertices and possibly loops, yielding an expression that matches the number of proper colorings for all positive integers k. The result is independent of the choice of edges or reduction order, confirming the well-definedness of P_G(k) as a polynomial of degree equal to the number of vertices in G.[8]History
Origins in graph coloring
The study of graph coloring originated in the late 19th century as mathematicians sought to resolve the four-color theorem, which posits that any map can be colored with at most four colors such that no adjacent regions share the same color. In the 1880s, Peter Guthrie Tait advanced this area by examining edge colorings of cubic (3-regular) planar graphs, demonstrating that the four-color theorem is equivalent to the statement that every bridgeless cubic planar graph is 3-edge-colorable.[10] Tait's approach transformed the vertex-coloring problem of maps into an edge-coloring problem on their dual graphs, providing an early combinatorial framework for enumerating colorings without explicitly using polynomials.[10] Building on these foundations, George David Birkhoff introduced the concept of the chromatic polynomial in 1912 to quantify the number of proper vertex colorings of a graph as a function of the number of available colors, specifically targeting an algebraic proof of the four-color theorem for planar graphs. Birkhoff's formulation expressed the count of colorings via a determinant of a matrix derived from the graph's structure, offering a tool to bound the polynomial at four colors and thereby establish non-negativity for planar maps. This innovation shifted focus from qualitative colorability to quantitative enumeration, motivated primarily by the need to analyze map colorings systematically. In 1932, Hassler Whitney generalized and formalized Birkhoff's chromatic polynomial as an intrinsic invariant of arbitrary graphs, independent of planarity, and established key properties such as its monic nature and deletion-contraction recurrence. Whitney's work emphasized the polynomial's role in capturing the essence of proper colorings—assignments of colors to vertices such that no adjacent vertices share the same color—extending its utility beyond map problems to broader graph-theoretic inquiries. These early developments laid the groundwork for using chromatic enumeration to tackle scheduling and resource allocation modeled as graph colorings, though the primary impetus remained the four-color challenge.Key developments and contributors
In 1968, Ronald C. Read published a seminal expository paper that revitalized interest in chromatic polynomials by deriving their key properties, exploring computational methods for their evaluation, and providing explicit expressions for classes of graphs such as trees, where the polynomial simplifies to k(k-1)^{n-1} for a tree with n vertices and k colors.[11] During the 1960s and 1970s, Sami Beraha advanced the understanding of chromatic roots through his investigations into the four-color problem for planar graphs, introducing the Beraha numbers—such as B_4 = 4, B_5 = 2 + \sqrt{2}, and subsequent terms defined by B_n = 2 + 2\cos(2\pi/n)—which identify potential accumulation points of non-integer real roots of chromatic polynomials for recursively constructible planar triangulations. In the mid-20th century, W. T. Tutte deepened connections between chromatic polynomials and broader algebraic structures by extending the dichromatic polynomial (now known as the Tutte polynomial) to matroids and exploring its universal properties, as detailed in his monograph on graph polynomials, which unified deletion-contraction recurrences across graphs and matroids while relating evaluations to chromatic counts. The 2000s saw the introduction of categorification techniques inspired by Khovanov's homology for links, with Laure Helme-Guizon and Yongwu Rong constructing graded cohomology groups for graphs whose Euler characteristic recovers the chromatic polynomial, thereby lifting the invariant to a richer homological structure.[12] Recent developments through 2025 include quantum algorithms leveraging string-net condensation and Fibonacci anyon braiding to approximate evaluations of chromatic polynomials for complex graphs, enabling scalable sampling that classical methods struggle with due to exponential growth.[13]Examples
Trees and paths
Trees provide simple yet illustrative examples for understanding the chromatic polynomial, as they are connected acyclic graphs. The path graph P_n, which consists of n vertices connected in a linear chain, has chromatic polynomial P_{P_n}(k) = k(k-1)^{n-1}. This formula arises from direct enumeration of proper colorings: the endpoint vertex can be colored in k ways, and each of the remaining n-1 vertices must differ in color from its unique neighbor, offering k-1 choices each.[1] More generally, every tree T on n vertices shares the identical chromatic polynomial P_T(k) = k(k-1)^{n-1}, regardless of the specific tree structure. This uniformity can be established using the deletion-contraction recurrence: removing a leaf edge disconnects the graph into a smaller tree and an isolated vertex, whose chromatic polynomials multiply appropriately under the recurrence, leading by induction to the stated formula.[14] Alternatively, the result follows from counting rooted trees in colorings, where one vertex is chosen as root (k choices) and the remaining n-1 vertices are assigned colors differing from their parent (k-1 choices each).[14] Trees are bipartite graphs, meaning their chromatic number is 2—they require at least two colors for a proper coloring but admit no odd cycles that would demand more. However, the chromatic polynomial P_T(k) enumerates all proper k-colorings for any positive integer k, yielding positive values for all k \geq 2 while vanishing at k = 0 and k = 1. This polynomial is monic of degree n, with leading term k^n, reflecting the total unrestricted colorings minus constraints from the n-1 edges. To illustrate, consider small paths (which are trees) and the number of proper colorings:- For n=1 (isolated vertex): P(k) = k, so 2 colors yield 2 colorings.
- For n=2 (single edge): P(k) = k(k-1), so 2 colors yield 2 colorings.
- For n=3 (path of three vertices): P(k) = k(k-1)^2, so 2 colors yield 2 colorings.
- For n=4 (path of four vertices): P(k) = k(k-1)^3, so 2 colors yield 2 colorings.
Cycles and complete graphs
The chromatic polynomial for the cycle graph C_n with n \geq 3 vertices is given byP_{C_n}(k) = (k-1)^n + (-1)^n (k-1),
where k is the number of available colors.[15] This formula arises from the deletion-contraction recurrence relation, which states that for any graph G and edge e, P_G(k) = P_{G-e}(k) - P_{G/e}(k), where G-e is G with edge e deleted and G/e is G with e contracted.[16] Applying this recursively to C_n reduces the problem to computing the polynomial for a path graph P_{n-1}, which has the form P_{P_m}(k) = k(k-1)^{m-1}.[15] The resulting expression exhibits an oscillatory behavior due to the alternating sign term, reflecting the cyclic structure: for even n, the polynomial evaluates positively for k \geq 2, while for odd n, it requires k \geq 3 for positive values, aligning with the chromatic number of even and odd cycles, respectively.[15] A special case occurs when n=3, where C_3 is isomorphic to the complete graph K_3, the triangle. Substituting into the cycle formula yields P_{C_3}(k) = (k-1)^3 + (-1)^3 (k-1) = k(k-1)(k-2), confirming the equivalence.[15] This derivation via deletion-contraction provides an inductive proof, starting from smaller cycles and building up, and can also be obtained through inclusion-exclusion principles counting colorings where adjacent vertices differ.[15] For the complete graph K_n with n vertices, where every pair of vertices is adjacent, the chromatic polynomial is the falling factorial
P_{K_n}(k) = k(k-1)(k-2) \cdots (k-n+1) = k^{\underline{n}}.
This follows directly from sequential vertex coloring: the first vertex has k choices, the second has k-1 (to differ from the first), the third has k-2 (to differ from the first two), and so on, up to the n-th vertex with k-n+1 choices.[16] The product form highlights the binomial nature, as it equals \frac{k!}{(k-n)!} for integer k \geq n, emphasizing the need for at least n colors to properly color K_n.[16] As an extension involving both cycles and complete subgraphs, the wheel graph W_n (a cycle C_n with an additional hub vertex connected to all rim vertices) has chromatic polynomial
P_{W_n}(k) = k \left[ (k-2)^n + (-1)^n (k-2) \right].
This can be derived by first coloring the hub ( k choices), then the rim as a cycle with restricted colors avoiding the hub's color ( k-2 effective colors), incorporating the cycle formula adjusted for the constraints.[17]
Properties
Fundamental theorems
The chromatic polynomial exhibits multiplicativity with respect to disjoint unions of graphs. Specifically, if G and H are two graphs with no vertices in common, then the chromatic polynomial of their disjoint union satisfies P_{G \cup H}(k) = P_G(k) \cdot P_H(k).[4] This property extends to disconnected graphs: if G consists of connected components C_1, C_2, \dots, C_m, then P_G(k) = \prod_{i=1}^m P_{C_i}(k).[4] A proof sketch follows from the definition of proper colorings: since the components are independent, the total number of ways to color G with k colors is the product of the numbers for each component, as color assignments to vertices in different components impose no restrictions on each other.[4] The chromatic polynomial P_G(k) is always a monic polynomial of degree n, where n = |V(G)| is the number of vertices in G. Thus, it can be expressed as P_G(k) = k^n + a_{n-1} k^{n-1} + \cdots + a_1 k + a_0, with leading coefficient 1. To see this, note that the total number of vertex colorings without adjacency restrictions is k^n, and the deletion-contraction recurrence subtracts terms that account for invalid colorings, preserving the degree and leading term by induction on the number of edges.[4] The coefficients of the chromatic polynomial alternate in sign. In the expansion P_G(k) = \sum_{i=0}^n (-1)^{n-i} a_i k^i, the a_i are nonnegative integers, with a_n = [1](/page/1) and a_0 = 0 for n \geq [1](/page/1). Stanley's theorem provides a combinatorial interpretation: the absolute values a_i count the number of acyclic orientations of G with exactly i sinks (or equivalently, via duality, relate to broken cycle structures). A proof uses inclusion-exclusion on cycles in the graph, showing that the signed coefficients arise from overcounting colorings that violate independence along circuit edges, with induction on the number of vertices confirming the alternation.[18] Evaluating the chromatic polynomial at k=1 yields P_G(1) = 0 if G has at least one edge, and P_G(1) = 1 if G is edgeless.[4] This follows directly from the coloring interpretation: with one color, all vertices must receive the same color, which is proper only if no edges exist to connect same-colored adjacent vertices; in the edgeless case, there is exactly one such coloring. For disconnected graphs, the multiplicativity ensures the result holds as long as any component has an edge.[4]Chromatic equivalence and roots
Two graphs G and H are said to be chromatically equivalent if they have the same chromatic polynomial, denoted P_G(k) = P_H(k) for all k, even if G and H are not isomorphic.[19] This phenomenon highlights that the chromatic polynomial does not uniquely determine the isomorphism class of a graph.[20] A classic example occurs with trees: all trees on n vertices are chromatically equivalent, sharing the polynomial P(k) = k(k-1)^{n-1}, regardless of their specific structure.[21] For n=4, the path graph P_4 and the star graph K_{1,3} provide a pair of non-isomorphic chromatically equivalent graphs, both with P(k) = k(k-1)^3.[22] The roots of the chromatic polynomial P_G(k), known as chromatic roots, are the complex numbers \alpha satisfying P_G(\alpha) = 0.[23] These roots are algebraic integers, and their locations in the complex plane have been extensively studied, with known bounds excluding certain regions such as the disk |z - 1| < 1 except for specific cases.[24] For planar graphs, the four-color theorem implies that there are no chromatic roots at integers greater than or equal to 5, as P_G(k) > 0 for all integers k \geq 5.[25] More refined conjectures address real chromatic roots; for instance, it is conjectured that planar graphs have no real roots in the interval (4, 5), building on the theorem's assurance that 4 is not a root.[26] In the context of planar triangulations, chromatic roots exhibit intriguing asymptotic behavior, often approaching the Beraha numbers, defined as B_n = 2 + 2 \cos \frac{2\pi}{n} for positive integers n.[27] These numbers arise as potential accumulation points of roots for sequences of triangulations with increasing vertices, with early Beraha numbers including B_4 = 3, B_5 \approx 2.618, and B_7 \approx 2.247.[28] The four-color theorem connects to this framework, as the absence of roots exceeding 4 aligns with roots clustering near 0, 1, 2, 3, or higher Beraha numbers rather than values greater than 4.[25] Numerical investigations into these root distributions for planar graphs have persisted into the 2020s, refining understandings of their density and limits, though comprehensive resolutions of related conjectures remain open.[29]Surjective colorings
The surjective chromatic polynomial of a graph G, denoted P_G^{\surj}(k), enumerates the proper vertex colorings of G using exactly k distinguishable colors, meaning every color is assigned to at least one vertex.[30] This variant emphasizes colorings where the color assignment is surjective onto the set of k colors, distinguishing it from the standard chromatic polynomial P_G(k), which permits unused colors.[31] The surjective chromatic polynomial relates to the standard one via inclusion-exclusion: P_G^{\surj}(k) = \sum_{m=0}^k (-1)^{k-m} \binom{k}{m} P_G(m). This expression derives from subtracting overcounts of non-surjective colorings in the inclusion-exclusion framework applied to the image sizes of color maps.[31] Equivalently, P_G^{\surj}(k) = k! \, [S(G, k)](/page/Stirling_number), where [S(G, k)](/page/Stirling_number) denotes the graph Stirling number of the second kind, counting the partitions of V(G) into exactly k nonempty independent sets.[31] The coefficients of the chromatic polynomial connect to acyclic orientations through Stanley's theorem, where P_G(x) = \sum_k (-1)^{|V|-k} a_k x^k and a_k is the number of acyclic orientations of G with k components.[18] For the surjective variant, the transformation via Stirling numbers and inclusion-exclusion yields coefficients interpretable in terms of these orientations.[31] Such colorings correspond to surjective graph homomorphisms from G to the complete graph K_k. In the 2010s, results showed that mutual surjective homomorphisms between graphs imply identical chromatic polynomials, establishing a Cantor-Bernstein-like property for chromatic equivalence via these mappings.[32] Applications include fixed-k enumerations in combinatorial partition functions and analyzing graph invariants under homomorphism counts.[33]Categorification
Categorification of the chromatic polynomial involves constructing higher categorical structures, such as chain complexes or homology theories, that lift the polynomial to graded invariants whose Euler characteristic recovers the original counting function. In particular, chromatic homology provides a graded vector space H_*(G; k) for a graph G and integer k \geq 0, satisfying P_G(k) = \sum_i (-1)^i \dim H_i(G; k), where the dimensions are taken over a suitable ground field and depend polynomially on k.[34] This construction was introduced by Helme-Guizon and Rong in 2005, who defined graded cohomology groups for graphs via a chain complex based on cubical posets associated to the graph's edges, motivated by Khovanov's 2000 categorification of the Jones polynomial for links into Khovanov homology.[34] The resulting chromatic homology is analogous to Khovanov homology but adapted to graph structures, with chain groups generated by certain subgraphs or colorings that respect the deletion-contraction recurrence of the chromatic polynomial.[34] Key properties of chromatic homology include the recovery of the chromatic polynomial as its Euler characteristic and the provision of refined invariants through the ranks of the homology groups, which capture more detailed topological information than the polynomial alone.[34] For instance, the homology satisfies long exact sequences mirroring the deletion-contraction relation, ensuring compatibility with graph operations.[34] These ranks enable applications such as distinguishing pairs of chromatically equivalent graphs—those sharing the same chromatic polynomial but differing in structure—via non-isomorphic homology groups, as demonstrated for cochromatic polygon-trees and other examples over specific ground rings like \mathbb{A}_3. In the 2020s, extensions have addressed limitations in tying chromatic homology to broader algebraic topology, including developments in chromatic symmetric homology, which lifts Stanley's chromatic symmetric function and distinguishes graphs with identical symmetric functions while detecting planarity in certain cases.[29] Further advances include multipath cohomology for directed graphs, providing an oriented variant that builds on chromatic homology but accounts for arc directions, thus resolving its orientation-blindness.[35] Additionally, a 2025 spanning tree model reinterprets the chromatic complex using spanning trees, offering combinatorial generators that enhance computational and structural insights into the homology.[36]Computation
Recursive methods
The deletion-contraction recurrence provides the foundation for a recursive algorithm to compute the chromatic polynomial of a graph G. For a non-empty edge set, select an edge e; the polynomial satisfies P(G, k) = P(G \setminus e, k) - P(G / e, k), where G \setminus e is the graph with e deleted and G / e is the graph with e contracted by merging its endpoints into a single vertex (discarding any resulting loops). Base cases include the edgeless graph on n vertices, where P(G, k) = k^n, and graphs containing loops, where P(G, k) = 0. This recursive approach, based on the deletion-contraction recurrence, builds a recursion tree by repeatedly applying the relation until base cases are reached, with the final polynomial obtained by combining results via subtraction.[4][8][7] To mitigate redundant computations in the recursion tree—where isomorphic subgraphs may arise multiple times—implementations employ memoization, storing the chromatic polynomials of encountered subgraphs (often represented in canonical form) for reuse. This dynamic programming technique significantly reduces the effective number of unique subgraph evaluations, though the overall space required grows with the number of distinct subgraphs.[21] The time complexity of the basic recursive algorithm is exponential. In the worst case, such as for dense graphs, it requires O(n^2 B(n)) operations, where B(n) is the nth Bell number counting set partitions (growing asymptotically faster than c^n for any constant c but slower than n!); this arises from the branching factor and the need to process up to B(n) partitions in the recursion. For sparse graphs with m \ll n^2 edges, the complexity improves to roughly O(2^m), as the recursion depth and branching are bounded by the edge count.[37] Optimizations enhance efficiency for practical computations. Parallelization exploits the independent deletion and contraction branches, allowing simultaneous evaluation on multi-core systems to halve the effective time for balanced trees. Additionally, graph symmetries via automorphism groups reduce redundant branches by identifying equivalent edges or subgraphs for selective recursion, often using canonical labeling to prune isomorphic cases during memoization.[37] Software tools implement these recursive methods effectively. SageMath provides a built-inchromatic_polynomial function using a recursive deletion-contraction approach optimized with observations on edge ordering to minimize branching. The nauty package supports symmetry detection through graph canonization, which integrates with recursive implementations (e.g., in Maple or custom codes) to enable efficient memoization by avoiding duplicate computations on automorphic subgraphs.[38][39]
As an illustrative example, consider the 4-cycle graph C_4 with vertices u, v, w, x and edges uv, vw, wx, xu. Apply deletion-contraction to edge uv:
- Deletion: C_4 \setminus uv is a 4-path (u-x-w-v), an edgeless graph after known path reduction, yielding P(C_4 \setminus uv, k) = k(k-1)^3.
- Contraction: C_4 / uv merges u and v into v', forming a triangle v'-w-x, with P(C_4 / uv, k) = k(k-1)(k-2).