Chromatic polynomial

The chromatic polynomial of a graph counts its proper vertex colorings as a function of the number of available colors. Its value at a positive integer counts colorings using at most that many colors.

Proper vertex coloring: An assignment of colors to graph vertices in which adjacent vertices receive different colors. The polynomial counts these assignments for each number of available colors.
Graph theory: The mathematical study of graphs, structures made of vertices joined by edges. Chromatic polynomials turn a graph’s adjacency structure into a counting function.
Planar graph: A graph that can be drawn in the plane without edges crossing except at shared endpoints. The four-color theorem asserts every planar graph has a proper coloring with at most four colors.
Francis Guthrie: A South African mathematician who posed the four-color problem after noticing a map-coloring puzzle in 1852. His map-coloring question helped motivate the search for systematic coloring counts.
Chromatic symmetric function: A symmetric function that encodes proper colorings of a graph using variables to record color assignments. It retains color-variable information that the chromatic polynomial compresses into one parameter.
Deletion–contraction recurrence: A recurrence that relates a graph invariant to its values on a graph with an edge deleted and one with that edge contracted. For a non-loop edge, chromatic polynomials satisfy this recurrence, enabling recursive calculation.
Graph: A structure consisting of vertices and edges that connect pairs of vertices. The polynomial is defined for a graph and depends on its vertices and edges.
Four color theorem: The theorem that every planar graph can be properly colored with at most four colors. It guarantees a positive chromatic-polynomial value at four for every planar graph.
Arthur Cayley: A British mathematician whose work included early investigations of graph coloring and enumeration. Cayley studied coloring questions that contributed to the polynomial’s early development.
Edge coloring: An assignment of colors to graph edges in which edges sharing a vertex receive different colors. It colors edges rather than vertices, so its counting polynomial captures a different constraint.

Linked from 5 pages