= Solution
Factor the proposed polynomial:
$$
f(t)=t(t-1)^2(t-2).
$$
In particular,
$$
f(2)=0.
$$
By the <two-colourability criterion for bipartite graphs>, every finite <bipartite graph> has at least one proper two-colouring, so its chromatic polynomial is positive at $2$. Therefore $f$ cannot be the chromatic polynomial of a bipartite graph.
It is nevertheless a chromatic polynomial. Start with the <complete graph> $K_3$, whose vertices may be coloured in
$$
t(t-1)(t-2)
$$
ways, and attach one <leaf of a graph>[leaf] to any vertex. After the triangle is coloured, the leaf has $t-1$ available colours. The <chromatic polynomial after attaching a leaf> therefore gives
$$
\boxed{P_G(t)=t(t-1)(t-2)(t-1)=f(t).}
$$
Back to article page
