Skip to main content
Mathematics LibreTexts

5.3: Deletion-Contraction and the Chromatic Polynomial

  • Page ID
    6117
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \(\rightarrow\) Exercise 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\). 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\). 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\). (Hint).

    Exercise 244

    Use the deletion-contraction recurrence to reduce the computation of the chromatic polynomial of the graph in Figure 5.3.1 to computation of chromatic polynomials that you can easily compute. (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.)

    150059470278565.png
    Figure \(\PageIndex{1}\): A graph. (Copyright; author via source)

    \(\rightarrow\) Exercise 245

    1. 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.
    2. (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.

    Exercise 246

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

    \(\rightarrow\) Exercise 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.

    Contributors and Attributions


    This page titled 5.3: Deletion-Contraction and the Chromatic Polynomial is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Kenneth P. Bogart.