I'm doing a university assignment and I thought I was good at graph coloring until I attempted these questions.
Let Cn be the cycle graph with n vertices and n edges and let Pn(x) be its chromatic polynomial.
(a) Explain why P3(x) = x (x − 1) (x − 2).
So this is quite simple, as all edges are attached so by the time you get to the last vertex you can use x-2 colors, so I'm alright with this.
(b) If n > 3 , describe the two graphs that are obtained when one ‘cuts Cn open along an edge’ and then ‘stitches it back up.’
This is what has me stumped, n > 3 allows for an infinite amount of answers? If someone could explain to me how to answer this, that would be awesome. If I could understand this question I could answer C, D.
(c) Hence find an expression for Pn(x) in terms of Pn−1(x) and another polynomial.
(d) Hence prove by Induction that Pn(x) = (x − 1)n + (−1)n(x − 1) for all n ≥ 3
(e) In how many ways can the cycle graph with 11 vertices be colored using 10 colours?
Any help you can provide would be greatly appreciated.
Let $P(G)$ be the chromatic polynomial of graph $G$.
Since $$P(G)=P(G-e)-P(G\cdot e)$$ (where $G-e$ is the graph you get after removing edge $e$ from $G$, and $G\cdot e$ is the graph you get after gluing the two vertices of $e$ into one), I think the two graphs part (b) is asking for are (1) the graph you get after removing $e$ from $C_n$ (i.e. $P_n$, the path graph with $n$ vertices and $n-1$ edges), and (2) the graph you get after gluing the two adjacent vertices together from $C_n$ (i.e. $C_{n-1}$).
So for part (c) you can get the expression of $P_n(x)$ in terms of these two graphs. Since $C_n-e=P_n$ and $C_n\cdot e=C_{n-1}$, you get $$P(C_n)=P(C_n-e)-P(C_n\cdot e)=P(P_n)-P(C_{n-1})$$.