Skip to main content
\(\newcommand{\cycle}[1]{\arraycolsep 5 pt \left(\begin{array}#1\end{array}\right)} \newcommand{\importantarrow}{\Rightarrow} \newcommand{\qchoose}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q} \def\neg1choose#1#2{\genfrac{[}{]}{0pt}{}{#1}{#2}_{-1}} \newcommand{\bp}{ \begin{enumerate}{\setcounter{enumi}{\value{problemnumber}}}} \newcommand{\ep}{\setcounter{problemnumber}{\value{enumi}} \end{enumerate}} \newcommand{\ignore}[1]{} \renewcommand{\bottomfraction}{.8} \renewcommand{\topfraction}{.8} \newcommand{\apple}{\text{🍎}} \newcommand{\ap}{\apple} \newcommand{\banana}{\text{🍌}} \newcommand{\ba}{\banana} \newcommand{\pear}{\text{🍐}} \newcommand{\pe}{\pear} \DeclareMathOperator{\Fix}{Fix} \DeclareMathOperator{\Orb}{Orb} \newcommand{\F}{\mathcal{F}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section 5.3 Deletion-Contraction and the Chromatic Polynomial

Problem 243

In Chapter 2 we introduced the deletion-contraction recurrence for counting spanning trees of a graph. Figure out how the chromatic polynomial of a graph is related to those resulting from deletion of an edge \(e\) and from contraction of that same edge \(e\text{.}\) Try to find a recurrence like the one for counting spanning trees that expresses the chromatic polynomial of a graph in terms of the chromatic polynomials of \(G-e\) and \(G/e\) for an arbitrary edge \(e\text{.}\) Use this recurrence to give another proof that the number of ways to color a graph with \(x\) colors is a polynomial function of \(x\text{.}\)

Hint

One way to get a proper coloring of \(G-e\) is to start with a proper coloring of \(G\) and remove \(e\text{.}\) But there are other colorings of \(G\) that become proper when you remove \(e\text{.}\)

Problem 244

Use the deletion-contraction recurrence to compute the chromatic polynomial of the graph in Figure 5.3.1. (You can simplify your computations by thinking about the effect on the chromatic polynomial of deleting an edge that is a loop, or deleting one of several edges between the same two vertices.)

Figure 5.3.1 A graph.
Problem 245
(a)

In how many ways may you properly color the vertices of a path on \(n\) vertices with \(x\) colors? Describe any dependence of the chromatic polynomial of a path on the number of vertices.

(b)

(Not tremendously hard.) In how many ways may you properly color the vertices of a cycle on \(n\) vertices with \(x\) colors? Describe any dependence of the chromatic polynomial of a cycle on the number of vertices.

Problem 246

In how many ways may you properly color the vertices of a tree on \(n\) vertices with \(x\) colors?

Hint

One approach would be to try to guess the result by doing a bunch of examples and use induction to prove you are right. If you try this, what will you be able to use to make the induction step work? There are other approaches as well.

Problem 247

What do you observe about the signs of the coefficients of the chromatic polynomial of the graph in Figure 5.3.1? What about the signs of the coefficients of the chromatic polynomial of a path? Of a cycle? Of a tree? Make a conjecture about the signs of the coefficients of a chromatic polynomial and prove it.