Lagmental Vicfred

The Chromatic Polynomial Satisfies Deletion--Contraction by Vicfred

tags: mathematics, graph enumeration, chromatic polynomials, matroids

Proper colorings split according to whether the endpoints of a chosen edge would have equal colors without that edge. This is a compact note, but the quantifiers and hypotheses stay on the page.

Statement

Graph invariants often satisfy deletion--contraction recurrences. The chromatic polynomial \(P_G(q)\) and Tutte polynomial \(T_G(x,y)\) package many counts into algebraic form.

$$ P_G(q)=\#\{\text{proper }q\text{-colorings of }G\} $$

There are two layers here: the object \(\mathsf D\) and the law \(\mathsf C\). Writing them separately makes the direction of \(\Longrightarrow\) visible and keeps an accidental converse from slipping in.

$$ P_G(q)=P_{G-e}(q)-P_{G/e}(q) $$

Worked algebra

Now evaluate one representative case. The result should agree with the structural law above, but it is obtained without assuming the conclusion.

$$ P_{C_n}(q)=(q-1)^n+(-1)^n(q-1) $$

Conceptual compression

What survives the example is not its particular numbers but the relation encoded by the two rows below. That relation is the part worth transporting to a new setting.

$$ \begin{aligned} \mathsf{D}\;&:\quad P_G(q)=\#\{\text{proper }q\text{-colorings of }G\},\\[5pt] \mathsf{C}\;&:\quad P_G(q)=P_{G-e}(q)-P_{G/e}(q). \end{aligned} $$

Caveat

Deletion--contraction must distinguish loops and bridges. Applying the generic edge recurrence to either special case changes the invariant incorrectly.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] P_G(q)=P_{G-e}(q)-P_{G/e}(q) \end{gathered}} $$

A symbolic summary is trustworthy only because the example and limitation remain visible beside it. The box compresses the conclusion without hiding its origin.

This article was posted on Tue 20 September 2011. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.