9
$\begingroup$

This is a homework question. But I am completely stuck.

My only intuition was to go about it inductively from a "greedy algorithm" maybe know as the deletion-contraction algorithm. And to somehow use the information about the jth cycle to solve the j+1th. But I'm not sure how I'd do it. Thank you very much for looking this over.

3 Answers 3

9

Let's denote $P(G,k)$ be the chromatic polynomial of a simple graph $G$. By deletion-contraction formula, given any edge $e$ in $G$, we have the following: $P(G,k)=P(G-e,k)-P(G\cdot e, k)$ where $G-e$ is the graph obtained by deleting $e$ in $G$, and $G\cdot e$ is the graph obtained by contracting $e$ in $G$.

To prove that $P(C_n,k)=(k-1)^{n} + (-1)^{n}(k-1)$, we use induction on $n$. For $n=3$, it's easy to see that we need to use different colors for different vertices. Therefore, $P(C_3,k)=k(k-1)(k-2)=(k-1)(k^2-2k)=(k-1)^3+(-1)^3(k-1).$ This proves the case when $n=3$.

Now assume that $P(C_n,k)=(k-1)^{n} + (-1)^{n}(k-1)$. Apply the deletion-contraction formula to $G=C_{n+1}$, we have $P(C_{n+1},k)=P(C_{n+1}-e,k)-P(C_{n+1}\cdot e, k).$ Note that the graph $C_{n+1}\cdot e$ is obtained by contracted an edge $e$ in $C_{n+1}$, which is isomorphic to $C_n$, which implies that $P(C_{n+1}\cdot e, k)=P(C_n,k)=(k-1)^{n} + (-1)^{n}(k-1).$ Note also that $C_{n+1}-e$ is the path $P_{n+1}$ with $n+1$ vertices, which implies that $P(C_{n+1}-e, k)=P(P_{n+1},k)=k(k-1)^n.$ (To see the last equality, we can use induction on number of vertices, or by simple counting argument: to color the end vertex, there are $k$ colors we can choose, then for the next one incident to the end vertex, there are $k-1$ colors we can choose, and so on.) Combining all these, we have $P(C_{n+1},k)=P(C_{n+1}-e,k)-P(C_{n+1}\cdot e, k)$ $=k(k-1)^n-(k-1)^{n}-(-1)^{n}(k-1)=(k-1)^{n+1} + (-1)^{n+1}(k-1),$ as required.

  • 0
    I think there's an error: $k(k-1)(k-2) \neq (k-1)(k^2 - k)$2017-05-28
6

You're on the right track. As far as I'm aware the greedy algorithm for finding a colouring and the deletion–contraction algorithm for counting them are two quite distinct algorithms. The deletion–contraction algorithm is exactly what you need. If you delete an edge in a cycle, the colourings of the remaining graph are straightforward to count, whereas if you contract an edge, you get a cycle with one fewer vertex. Thus you get a recurrence relation that expresses the number of colourings of $C_n$ as the number of colourings of $C_{n-1}$ plus a known expression. Then, since you already know the solution, you just have to verify that it solves this recurrence, and that it's correct for $n=2$.

  • 0
    @bill: A cycle with one edge deleted is a chain. In how many ways can you colour the vertex at one end of the chain? How many ways does that leave for the vertex adjacent to it? And how many ways does that leave for the vertex after that? And so on...2011-12-13
1

You can also do this directly using the principle of inclusion–exclusion. Label the vertices of $C_n$ sequentially using the integers $0$, $1$, ..., $n-1$. For $S\subseteq\{0,1,\ldots,n-1\}$, let $T_S$ be the set of colorings (proper or improper) of $C_n$ in which, for each $j\in S$, the color of vertex $j$ is the same as that of vertex $j-1$ (with arithmetic performed mod $n$). The number of proper colorings is then $ \lvert T_{\{\}}\rvert-\sum_{i=0}^{n-1}\lvert T_{\{i\}}\rvert+\sum_{0\le i Now there are $\binom{n}{m}$ different $S$ of size $m$. Furthermore, $ \lvert T_S\rvert=\begin{cases}k^{n-\lvert S\rvert} & \text{if $\lvert S\rvert Hence the number of proper colorings is $ (-1)^nk+\sum_{m=0}^{n-1}\binom{n}{m}k^{n-m}(-1)^m $ The result follows immediately from the binomial theorem.