zbMATH — the first resource for mathematics

On the chromaticity of certain subgraphs of a q-tree. (English) Zbl 0698.05029
It is known that the chromatic polynomial of triangulated graphs has only integral roots, but the converse doesn’t hold. The author gives here a new family of graphs for which the converse is also true. Namely, he proved that a graph G on \(n\geq q+1\) vertices (q\(\geq 2)\) has the chromatic polynomial \(P(G;\lambda)=\lambda (\lambda -1)...(\lambda -q+2)(\lambda - q+1)^ 2(\lambda -q)^{n-q-1}\) if and only if G is obtained from a q- tree on n vertices by deleting an edge contained in exactly q-1 triangles; furthermore such a graph is triangulated.
Reviewer: C.Radu

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Chao, J. Graph Theory 10 pp 129– (1986)
[2] Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). · Zbl 0541.05054
[3] Graph Theory. Addison-Wesley, Reading, MA (1969).
[4] Read, J. Combinat. Theory 4 pp 52– (1968)
[5] Vaderlind, J. Graph Theory 12 pp 245– (1988)
[6] Whitehead, J. Graph Theory 9 pp 279– (1985)
[7] Whitehead, J. Graph Theory 8 pp 371– (1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.