On the chromaticity of certain subgraphs of a q-tree

1. Thomas Wanner:
   On the chromaticity of certain subgraphs of a q-tree
   Journal of Graph Theory 13(5), pp. 597-605, 1989.

Abstract

We show that a graph $G$ on $n \ge q+1$ vertices (where $q \ge 2$) has the chromatic polynomial $P(G;\lambda) = \lambda (\lambda-1) \cdot \ldots \cdot (\lambda-q+2) (\lambda-q+1)^2 (\lambda-q)^{n-q-1}$ if and only if $G$ can be obtained from a $q$-tree $T$ on $n$ vertices by deleting an edge contained in exactly $q−1$ triangles of $T$. Furthermore, we prove that these graphs are triangulated.

Links

The published version of the paper can be found at https://doi.org/10.1002/jgt.3190130510.

Bibtex

@article{wanner:89a,
   author = {Thomas Wanner},
   title = {On the chromaticity of certain subgraphs of a q-tree},
   journal = {Journal of Graph Theory},
   year = 1989,
   volume = 13,
   number = 5,
   pages = {597--605},
   doi = {10.1002/jgt.3190130510}
   }