Chromatic polynomial
Function in algebraic graph theory / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Chromatic polynomial?
Summarize this article for a 10 year old
The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to study the four color problem. It was generalised to the Tutte polynomial by Hassler Whitney and W. T. Tutte, linking it to the Potts model of statistical physics.
George David Birkhoff introduced the chromatic polynomial in 1912, defining it only for planar graphs, in an attempt to prove the four color theorem. If denotes the number of proper colorings of G with k colors then one could establish the four color theorem by showing for all planar graphs G. In this way he hoped to apply the powerful tools of analysis and algebra for studying the roots of polynomials to the combinatorial coloring problem.
Hassler Whitney generalised Birkhoff’s polynomial from the planar case to general graphs in 1932. In 1968, Ronald C. Read asked which polynomials are the chromatic polynomials of some graph, a question that remains open, and introduced the concept of chromatically equivalent graphs.[1] Today, chromatic polynomials are one of the central objects of algebraic graph theory.[2]
For a graph G, counts the number of its (proper) vertex k-colorings. Other commonly used notations include , , or . There is a unique polynomial which evaluated at any integer k ≥ 0 coincides with ; it is called the chromatic polynomial of G.
For example, to color the path graph on 3 vertices with k colors, one may choose any of the k colors for the first vertex, any of the remaining colors for the second vertex, and lastly for the third vertex, any of the colors that are different from the second vertex's choice. Therefore, is the number of k-colorings of . For a variable x (not necessarily integer), we thus have . (Colorings which differ only by permuting colors or by automorphisms of G are still counted as different.)
Deletion–contraction
The fact that the number of k-colorings is a polynomial in k follows from a recurrence relation called the deletion–contraction recurrence or Fundamental Reduction Theorem.[3] It is based on edge contraction: for a pair of vertices and the graph is obtained by merging the two vertices and removing any edges between them. If and are adjacent in G, let denote the graph obtained by removing the edge . Then the numbers of k-colorings of these graphs satisfy:
Equivalently, if and are not adjacent in G and is the graph with the edge added, then
This follows from the observation that every k-coloring of G either gives different colors to and , or the same colors. In the first case this gives a (proper) k-coloring of , while in the second case it gives a coloring of . Conversely, every k-coloring of G can be uniquely obtained from a k-coloring of or (if and are not adjacent in G).
The chromatic polynomial can hence be recursively defined as
- for the edgeless graph on n vertices, and
- for a graph G with an edge (arbitrarily chosen).
Since the number of k-colorings of the edgeless graph is indeed , it follows by induction on the number of edges that for all G, the polynomial coincides with the number of k-colorings at every integer point x = k. In particular, the chromatic polynomial is the unique interpolating polynomial of degree at most n through the points
Tutte’s curiosity about which other graph invariants satisfied such recurrences led him to discover a bivariate generalization of the chromatic polynomial, the Tutte polynomial .
Triangle | |
Complete graph | |
Edgeless graph | |
Path graph | |
Any tree on n vertices | |
Cycle | |
Petersen graph |
For fixed G on n vertices, the chromatic polynomial is a monic polynomial of degree exactly n, with integer coefficients.
The chromatic polynomial includes at least as much information about the colorability of G as does the chromatic number. Indeed, the chromatic number is the smallest positive integer that is not a zero of the chromatic polynomial,
The polynomial evaluated at , that is , yields times the number of acyclic orientations of G.[4]
The derivative evaluated at 1, equals the chromatic invariant up to sign.
If G has n vertices and c components , then
- The coefficients of are zeros.
- The coefficients of are all non-zero and alternate in signs.
- The coefficient of is 1 (the polynomial is monic).
- The coefficient of is .
We prove this via induction on the number of edges on a simple graph G with vertices and edges. When , G is an empty graph. Hence per definition . So the coefficient of is , which implies the statement is true for an empty graph. When , as in G has just a single edge, . Thus coefficient of is . So the statement holds for k = 1. Using strong induction assume the statement is true for . Let G have edges. By the contraction-deletion principle,
,
Let , and .
Hence .
Since is obtained from G by removal of just one edge e, , so and thus the statement is true for k.
- The coefficient of is times the number of acyclic orientations that have a unique sink, at a specified, arbitrarily chosen vertex.[5]
- The absolute values of coefficients of every chromatic polynomial form a log-concave sequence.[6]
The last property is generalized by the fact that if G is a k-clique-sum of and (i.e., a graph obtained by gluing the two at a clique on k vertices), then
A graph G with n vertices is a tree if and only if
Chromatic equivalence
Two graphs are said to be chromatically equivalent if they have the same chromatic polynomial. Isomorphic graphs have the same chromatic polynomial, but non-isomorphic graphs can be chromatically equivalent. For example, all trees on n vertices have the same chromatic polynomial. In particular, is the chromatic polynomial of both the claw graph and the path graph on 4 vertices.
A graph is chromatically unique if it is determined by its chromatic polynomial, up to isomorphism. In other words, G is chromatically unique, then would imply that G and H are isomorphic. All cycle graphs are chromatically unique.[7]
Chromatic roots
A root (or zero) of a chromatic polynomial, called a “chromatic root”, is a value x where . Chromatic roots have been very well studied, in fact, Birkhoff’s original motivation for defining the chromatic polynomial was to show that for planar graphs, for x ≥ 4. This would have established the four color theorem.
No graph can be 0-colored, so 0 is always a chromatic root. Only edgeless graphs can be 1-colored, so 1 is a chromatic root of every graph with at least one edge. On the other hand, except for these two points, no graph can have a chromatic root at a real number smaller than or equal to 32/27.[8] A result of Tutte connects the golden ratio with the study of chromatic roots, showing that chromatic roots exist very close to : If is a planar triangulation of a sphere then
While the real line thus has large parts that contain no chromatic roots for any graph, every point in the complex plane is arbitrarily close to a chromatic root in the sense that there exists an infinite family of graphs whose chromatic roots are dense in the complex plane.[9]
Colorings using all colors
For a graph G on n vertices, let denote the number of colorings using exactly k colors up to renaming colors (so colorings that can be obtained from one another by permuting colors are counted as one; colorings obtained by automorphisms of G are still counted separately). In other words, counts the number of partitions of the vertex set into k (non-empty) independent sets. Then counts the number of colorings using exactly k colors (with distinguishable colors). For an integer x, all x-colorings of G can be uniquely obtained by choosing an integer k ≤ x, choosing k colors to be used out of x available, and a coloring using exactly those k (distinguishable) colors. Therefore:
- ,
where denotes the falling factorial. Thus the numbers are the coefficients of the polynomial in the basis of falling factorials.
Let be the k-th coefficient of in the standard basis , that is:
Stirling numbers give a change of basis between the standard basis and the basis of falling factorials. This implies:
- and .
Categorification
The chromatic polynomial is categorified by a homology theory closely related to Khovanov homology.[10]