Chromatic recurrence

Question

1) How do you prove the Chromatic recurrence theorem: $$χ(G;k)=χ(G−e;k)−χ(G·e;k)$$

I'm thinking by induction, but then you would have to assume something about the type of graph G...surely it can't be done any other way?

2) (See below - please ignore my numbering)! Let this graph be G.

Find an explicit formula for $χ(G;t)$.

My answer: $χ(G;k) = k(k-1)(k-2)^2(k-3)^2$

Is this correct? Or is this not an 'explicit' formula?

Answer 1

For 2) I would choose to use a different formulation of 1); Addition-Identification: $$P(H-e,x) = P(H,x) + P(H/e,x)$$ Note that this is the breakdown used in the proof of 1) by Andreas. It is usually better to use this to find the polynomial when the graph has a vertex joined to nearly all other vertices.

If we let $H$ be the graph with the two vertices of valency 4 joined by an edge then we can use the following equation: $$P(G,x) = P(K_2 +(2K_2),x) + P(K_1+(2K_2),x)$$

Now in both of these graphs there is a vertex joined to all others so we can use Total Adjacency which I explained in this answer: since $2K_2$ is two trees we must have $P(2K_2,x) = x^2(x-1)^2$ and thus $P(K_1+(2K_2),x) = x P(2K_2,x-1) = x(x-1)^2(x-2)^2$ and finally $$P(K_2+(2K_2),x) = P(K_1+(K_1+2K_2),x) = x(x-1)(x-2)^2(x-3)^2$$

Putting these two together we get:

$$P(G,x) = x(x-1)(x-2)^2(x-3)^2 + x(x-1)^2(x-2)^2 \\ = x(x-1)(x-2)^2(x^2-6x+9 + x-1) \\ = x(x-1)(x-2)^2(x^2-5x+8) $$

Note that this agrees with the numbers given by Andreas.

Answer 2

For (1), let $u$ and $v$ be the endpoints of the edge $e$, and notice that the proper $t$-colorings of $G-e$ are of two sorts: those that give $u$ and $v$ the same color, and those that don't. A coloring of the first sort, with the same color for $u$ and $v$, amounts to a proper coloring of what I call $G/e$ and you call $G\cdot e$, the graph obtained from $G$ by identifying the two vertices $u$ and $v$ and removing $e$ (which would otherwise be a loop at the identified vertex). On the other hand, a coloring of the second sort amounts to a proper coloring of $G$, i.e., it remains proper when you restore the edge $e$ to $G-e$ and thereby obtain the original $G$. Thus, the number of proper $t$-colorings of $G-e$ is the sum of the number of proper $t$-colorings of $G/e$ and the number of proper $t$-colorings of $G$. That (after transposing one term) is the equation in (1).

As for (2), your formula, in which $k$ was presumably intended to be $t$, can't be right, because it vanishes when $k$ (or $t$) is $3$, whereas the graph does have a proper $3$-coloring: Use color $3$ at the two vertices so labeled in your picture, color $1$ at the leftmost and rightmost vertices, and color $2$ at the top and bottom vertices.