A Brute-Force Method for Studying the Chromatic Properties Of Homeomorphic Graphs

Abstract

Let $M$ be a graph, and let $H(M)$ denote the homeomorphism class of $M$, that is, the set of all graphs obtained from $M$ by replacing every edge by a `chain’ of edges in series. Given $M$ it is possible, either using the `chain polynomial’ introduced by E. G. Whitehead and myself (Discrete Math. $204(1999)337-356)$ or by ad hoc methods, to obtain an expression which subsumes the chromatic polynomials of all the graphs in $H(M)$. It is a function of the number of colors and the lengths of the chains replacing the edges of $M$. This function contains complete information about the chromatic properties of these graphs. In particular, it holds the answer to the question “Which pairs of graphs in $H(M)$ are chromatically equivalent”. However, extracting this information is not an easy task.

In this paper, I present a method for answering this question. Although at first sight it appears to be wildly impractical, it can be persuaded to yield results for some small graphs. Specific results are given, as well as some general theorems. Among the latter is the theorem that, for any given integer $\gamma$, almost all cyclically $3$-connected graphs with cyclomatic number $\gamma$ are chromatically unique.

The analogous problem for the Tutte polynomial is also discussed, and some results are given.