Discrete Mathematics: An Open Introduction, fourth edition
Oscar Levin · Open textbook
Read fourth-edition §2.5 for proper coloring; use the triangle to distinguish chromatic number from count.
Open the sourceGraph coloring becomes a polynomial
Count once for a variable number of colors.
Prerequisites: 12 · Counting without listing everything, 13 · Graphs: connection and redundancy
Understand
Objectives
- Count proper colorings at a stated nonnegative integer q.
- Use deletion–contraction on a cycle with distinct edge endpoints.
- Distinguish chromatic polynomial from matroid characteristic polynomial when components differ.
Start with something you can see
Color a triangle’s vertices 1,2,3 from q labeled colors, keeping endpoints of each edge different. Choose the first in q ways, the next in q−1, and the last in q−2. Predict the count at q=3 before moving the graph lab’s color slider. To match the static table in the four-vertex lab, select edges 1–2, 2–3, 1–3 and leave vertex 4 isolated.
Give the idea a precise name
A proper vertex coloring assigns one of q available colors to every vertex so adjacent endpoints differ. For a nonnegative integer q, the chromatic polynomial P_G(q) counts these assignments. The chromatic number instead asks for the smallest q with any proper coloring. For an edge e joining distinct vertices, deletion removes its restriction; contraction identifies its endpoints.
P_G(q)=P_{G∖e}(q)−P_{G/e}(q)
Deletion admits every original coloring plus those with e’s endpoints equal. Those extra colorings correspond to colorings after contraction. A loop makes proper coloring impossible. Polynomial evaluation at nonnegative integer q counts assignments; signed polynomial coefficients are not counts of colorings. The graph’s matroid still has edges, while the color assignments belong to vertices.
Work one small world
For a triangle and one isolated vertex, the isolated vertex has q independent choices, so P(q)=q²(q−1)(q−2). The table gives exact counts for the lab configuration:
| q | Triangle | Isolated vertex choices | All four vertices |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 2 | 0 | 2 | 0 |
| 3 | 6 | 3 | 18 |
| 4 | 24 | 4 | 96 |
For the 4-cycle preset, delete one edge to get a path and contract it to get a triangle: P(q)=q(q−1)³−q(q−1)(q−2)=q⁴−4q³+6q²−3q. At q=3 it counts 18 colorings. Its absolute nonzero coefficients (1,4,6,3) ask a different, structural question.
Counterexample to “divide every chromatic polynomial by q to get the matroid polynomial”: the triangle plus isolated vertex has two components, and P(q)=q²(q−1)(q−2). Its graphic matroid has χ(q)=(q−1)(q−2); dividing by q only leaves an extra factor q. In general P_G(q)=qᶜχ_{M(G)}(q), where c counts components.
THE BRIDGEFlats and Möbius recursion extract χ from a matroid without first coloring any graph.
WHERE THIS IDEA STOPSOnly nonnegative integer q directly counts color assignments. Do not mistake absolute coefficients for evaluated counts.
Experiment
Set q to 0,1,2,3,4 in the graph lab after choosing 1–2, 2–3, 1–3. Compare with the table, then use the 4-cycle preset and predict the change at q=3.
Which forbidden colorings did deleting this edge accidentally admit?
Check & explain
How many proper 3-colorings does a triangle plus isolated vertex have?
What factor relates P_G(q) to χ of its graphic matroid when G has two components?
- q
- q²
- q−1
Teach back
Derive the 4-cycle polynomial by deletion–contraction, then add an isolated vertex and state how both P and χ change.
- Identify the path and triangle in the recurrence.
- Count the isolated vertex choices separately.
- Use qᶜ rather than silently assuming connectivity.
Read deeper
Hodge theory in combinatorics
Matthew Baker · Open research survey
Read Baker §3.2 for the chromatic-to-characteristic connection; track the component factor.
Open the sourceLec 6 | MIT 6.042J Mathematics for Computer Science, Fall 2010
MIT OpenCourseWare · Course lecture · MIT OCW
Use lecture 6 for proper vertex coloring, not the chromatic polynomial.
Open the source