HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Chromatic polynomial of a cycle - Interpreting its terms

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
cyclepolynomialinterpretingchromaticitsterms

Problem

I am learning about graph coloring. One of the exercise problems(grimaldi) led me to derive the chromatic polynomial for any cycle($C_n, n \ge 3$).

$P(C_n, \lambda) = (\lambda - 1)^n + (-1)^n(\lambda - 1)$, where $\lambda$ is the number of colours available

Is it possible to interpret the terms of above polynomial? I need help doing the same.

Solution

There is a theorem of Whitney answering your question. Let
$$ P(G,\lambda) = \sum_{k=0}^n (-1)^k a_k \lambda^{n-k}. $$
Then $a_k$ is the number of $k$-subsets of the edges of $G$ not containing any broken cycle. A broken cycle of $G$ is obtained from a cycle of $G$ by removing its maximum edge according to some fixed ordering of the edges.

For example, if $G = C_n$ then for $k < n-1$, $a_k = \binom{n}{k}$, and $a_{n-1} = \binom{n}{n-1} - 1$, since we miss one broken cycle.

For a proof and references to other proofs, see this paper.

Context

StackExchange Computer Science Q#4787, answer score: 2

Revisions (0)

No revisions yet.