Chromatic polynomial¶

A graph polynomial P(G,k) whose value at each nonnegative integer k counts the proper vertex colorings of graph G using k labeled colors.

Version: v2 · 2026-09-19 · History
Domain-specific #: 3681
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Algebraic Graph Theory → Mathematics

Core Idea¶

Chromatic polynomials satisfy deletion-contraction, factor over components and cut structures, specialize to chromatic number and acyclic orientations, and connect the Tutte polynomial with statistical-mechanical partition functions. Proper colorings partition assignments by an edge's endpoints being equal or unequal; deletion-contraction recursively expresses the count and interpolation extends the integer-valued counting function to a polynomial. The abstraction is therefore identified by a declared carrier, a transformation or constraint over that carrier, and an invariant that tells an analyst whether the named structure is genuinely present.

How would you explain it like I'm…

The Coloring Counter

Draw dots and connect some with lines. Now you have some crayons, and dots joined by a line can't share a color. The chromatic polynomial is a counting rule that tells you how many different ways there are to color the dots, for any number of crayons you pick.

Ways-to-Color Formula

Take a graph (dots joined by lines) and color every dot so that connected dots are different colors. With 2 crayons there may be a few ways, with 3 crayons more ways, and so on. The chromatic polynomial is one formula that tells you the number of good colorings for however many crayons you have. It can be worked out by looking at one line at a time: count colorings where the two ends could be anything, then remove the ones where they would match. The smallest crayon number that gives more than zero ways is the chromatic number.

Proper-Coloring Counting Polynomial

The chromatic polynomial P(G, k) counts the proper colorings of a graph G using k available colors, where proper means adjacent vertices get different colors. It turns out this count is always a polynomial in k. One way to compute it is deletion-contraction: pick an edge; colorings of the graph without that edge split into those where the edge's two endpoints differ (the ones we want) and those where they are equal (which is like merging the two endpoints into one vertex). So P(G) = P(G with the edge deleted) − P(G with the edge contracted). The polynomial also factors nicely when a graph splits into separate pieces. Plugging in values tells you things, such as the chromatic number: the smallest positive integer where it isn't zero.

The chromatic polynomial P(G, x) of a finite graph G counts proper vertex colorings from a set of x labeled colors, extended from positive integers to a polynomial by interpolation. Its structure comes from the deletion–contraction recurrence P(G) = P(G − e) − P(G / e), which follows from partitioning colorings of G − e by whether the endpoints of e receive equal or unequal colors; the base cases are edgeless graphs, where P = x^n. Consequences include that P factors as a product over connected components and factors across certain cut structures. It specializes to the chromatic number (the least positive integer that is not a root) and, through a suitable evaluation, to the number of acyclic orientations. It also links to the Tutte polynomial, of which it is a specialization, and to partition functions from statistical mechanics such as the Potts model. Results depend on conventions, such as how loops and multiple edges are treated, being fixed explicitly.

Scope of Application¶

Chromatic polynomial belongs to algebraic graph theory and is useful where the analyst can specify the typed algebraic graph theory carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, then evaluate the finite graph and loop or multiedge convention, labeled color set, proper-coloring predicate, variable and polynomial normalization, deletion-contraction base cases, degree and coefficients, evaluation domain, and any Tutte or Potts specialization are explicit. The scope is broad within that domain but bounded by the need for the finite graph and loop or multiedge convention, labeled color set, proper-coloring predicate, variable and polynomial normalization, deletion-contraction base cases, degree and coefficients, evaluation domain, and any Tutte or Potts specialization are explicit.

Clarity¶

The abstraction clarifies a crowded vocabulary by making the finite graph and loop or multiedge convention, labeled color set, proper-coloring predicate, variable and polynomial normalization, deletion-contraction base cases, degree and coefficients, evaluation domain, and any Tutte or Potts specialization are explicit the center of the account. A claim should name the carrier, the governing operation or relation, the applicable assumptions, and the recognition test.

Manages Complexity¶

Without the abstraction, an analyst must reason directly over many local details: the carrier roles, admissibility assumptions, competing conventions, derived invariants, boundary cases, and proof or validation obligations specific to Chromatic polynomial. Chromatic polynomial compresses them into the roles in the structural signature. That compression permits comparison across instances without erasing the variables that determine validity. It also exposes which details may be varied safely and which are constitutive.

Abstract Reasoning¶

Identify the carrier. State what the elements, states, objects, or observations are: the typed algebraic graph theory carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets. Reject examples whose alleged carrier belongs to a different problem.
Lock the constitutive rule. Express the finite graph and loop or multiedge convention, labeled color set, proper-coloring predicate, variable and polynomial normalization, deletion-contraction base cases, degree and coefficients, evaluation domain, and any Tutte or Potts specialization are explicit independently of one notation or implementation.

Knowledge Transfer¶

Knowledge transfers strongly among subfields of algebraic graph theory because they reuse the typed algebraic graph theory carrier, defining objects and relations, parameters, conventions, evidence, boundary cases, and comparison targets, Proper colorings partition assignments by an edge's endpoints being equal or unequal; deletion-contraction recursively expresses the count and interpolation extends the integer-valued counting function to a polynomial., and type the carrier, state every parameter and convention in the definition, test that the finite graph and loop or multiedge convention, labeled color set, proper-coloring predicate, variable and polynomial normalization, deletion-contraction base cases, degree and coefficients, evaluation domain, and any Tutte or Potts specialization are explicit, compare the nearest accepted identity, and report counterexamples, uncertainty, and limiting cases.

Relationships to Other Abstractions¶

Current abstraction Chromatic polynomial Domain-specific

Parents (1) — outgoing typed relations

Chromatic polynomial is a kind of Encoding And Decoding Prime

It remains its own entry because its identity is fixed by the finite graph and loop or multiedge convention, labeled color set, proper-coloring predicate, variable and polynomial normalization, deletion-contraction base cases, degree and coefficients, evaluation domain, and any Tutte or Potts specialization.

Hierarchy path (1) — routes to 1 parentless root

Chromatic polynomial → is a kind of Encoding And Decoding → includes Transformation → is a kind of, typical Function (Mapping)

Neighborhood in Abstraction Space¶

Chromatic polynomial sits in a crowded region of the domain-specific corpus (2^nd percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.

Family — Graph Coloring & Invariants (18 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25