A brute-force method for studying the chromatic properties of homeomorphic graphs

作者：Read Ronald C^*

来源：Ars Combinatoria, 2010, 96: 425-457.

• Chromatic polynomials
• Tutte polynomial
• chromatically equivalent
• graphs
• chromatically unique graphs
• homeomorphic graphs

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 gimel, 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.

• 出版日期2010-7