zbMATH — the first resource for mathematics

On q-trees. (English) Zbl 0591.05021
A q-tree is defined inductively as a complete graph \(K_ q\) on q vertices or as the graph G’ obtained from a q-tree G by adding a new vertex that is adjacent to all the vertices in some \(K_ q\) of G. The authors show that the chromatic polynomial \(P(G,\lambda)\) of a q-tree with n vertices \((n\geq q)\) is \(P(G,\lambda)=\lambda (\lambda - 1)...(\lambda -q+1)(\lambda -q)^{n-q}.\)
Reviewer: A.Tucker

05C05 Trees
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Graph Theory. Addison-Wesley, Reading, MA (1969).
[2] Read, J. Combinatorial Theory 4 pp 52– (1968) · Zbl 0165.32802
[3] Stirling numbers and coloring of q-trees, Prace Nauk. Inst. Mat. Politechn. Wroclaw, Ser. Stud. i Materi√Ĺ 13, Grafy, hipergrafy, system blokow (1977), pp. 63–67.
[4] Whitehead, J. Graph Theory 9 pp 279– (1985)
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.