Chromatic Polynomial and Edge Coloring

The chromatic polynomial encodes the number of proper colorings as a function of the number of colors. Edge coloring, a parallel theory, assigns colors to edges so that edges sharing a vertex receive different colors.

Chromatic Polynomial

Definition5.3Chromatic Polynomial

The chromatic polynomial $P(G, k)$ counts the number of proper $k$ -colorings of $G$ . Key properties: (1) $P(G, k)$ is a polynomial in $k$ of degree $n = |V|$ ; (2) the leading coefficient is 1; (3) the coefficient of $k^{n-1}$ is $-|E|$ ; (4) $\chi(G) = \min\{k \in \mathbb{Z}_+ : P(G, k) > 0\}$ . For connected $G$ : the coefficients alternate in sign and $P(G, k) > 0$ for all real $k > \chi(G) - 1$ .

ExampleDeletion-Contraction

The deletion-contraction recurrence: $P(G, k) = P(G - e, k) - P(G/e, k)$ for any edge $e$ . Base cases: $P(E_n, k) = k^n$ (empty graph), $P(K_n, k) = k(k-1)\cdots(k-n+1)$ . For the cycle $C_n$ : $P(C_n, k) = (k-1)^n + (-1)^n(k-1)$ . For a tree $T_n$ : $P(T_n, k) = k(k-1)^{n-1}$ .

Edge Coloring

Definition5.4Edge Chromatic Number

A proper edge coloring assigns colors to edges so that edges sharing a vertex get different colors. The chromatic index $\chi'(G)$ is the minimum number of colors needed. Since each vertex has degree $\Delta$ , we need $\chi'(G) \geq \Delta(G)$ . Vizing's theorem: $\chi'(G) \in \{\Delta(G), \Delta(G) + 1\}$ for simple graphs. Graphs with $\chi' = \Delta$ are Class 1; those with $\chi' = \Delta + 1$ are Class 2.

RemarkVizing's Classification

Classifying graphs as Class 1 or 2 is NP-complete. Known results: bipartite graphs are Class 1 (König's theorem), planar graphs with $\Delta \geq 7$ are Class 1 (Vizing), and the Petersen graph is Class 2 ( $\Delta = 3$ , $\chi' = 4$ ). Multigraphs satisfy $\chi'(G) \leq \lfloor 3\Delta/2 \rfloor$ (Shannon's theorem) and the stronger bound $\chi' \leq \Delta + \mu$ where $\mu$ is the maximum edge multiplicity.

List Coloring

Definition5.5List Chromatic Number

In list coloring, each vertex $v$ has a list $L(v)$ of permitted colors, and we seek a proper coloring with $c(v) \in L(v)$ . The list chromatic number $\chi_\ell(G) = \mathrm{ch}(G)$ is the minimum $k$ such that $G$ is $L$ -colorable for every assignment of lists of size $k$ . Always $\chi(G) \leq \chi_\ell(G)$ , but equality can fail: $\chi(K_{3,3}) = 2$ but $\chi_\ell(K_{3,3}) = 3$ . The list coloring conjecture asserts $\chi_\ell'(G) = \chi'(G)$ for every graph.

ExampleGalvin's Theorem

Galvin (1995) proved the list coloring conjecture for bipartite graphs: $\chi_\ell'(G) = \chi'(G) = \Delta(G)$ for bipartite $G$ . The proof uses a clever orientation argument and the theory of kernel-perfect graphs.