zbMATH — the first resource for mathematics

Classification of chromatically unique graphs having quadratic \(\sigma\)- polynomials. (English) Zbl 0686.05021
Let P(G) denote the chromatic polynomial of a finite simple graph. The graph G is called chromatically unique if \(P(G)=P(H)\) implies that G is isomorphic with H. Chromatically unique graphs have been studied by C.-Y. Chao and the second author [Lect. Notes Math. 642, 121-131 (1978; Zbl 0369.05032)].
Let the chromatic polynomial of a graph G with p vertices be given in terms of the factorial basis \(\{(\lambda)_ i:\) \(i=0,1,...\}\), where \((\lambda)_ i=\lambda (\lambda -1)...(\lambda -i+1)\) (i\(\geq 1)\), \((\lambda)_ 0=1\), and let \(\chi\) (G) denote the chromatic number of G. Then there are integers \(a_ 0,a_ 1,...,a_ h\) with \(P(G)=\sum^{h}_{i=1}a_ i(\lambda)_{p-i}\) where \(h=p-\chi (G).\) Now the \(\sigma\)-polynomial of G is defined by \(\sigma (G)=\sum^{h}_{i=0}a_ i\sigma^{h-i}\). R. W. Frucht and R. E. Giudici [Ars Comb. 16-A, 161-172 (1983; Zbl 0536.05026)] classified all graphs having quadratic \(\sigma\)-polynomials.
In the present paper such a characterization is given for all chromatically unique graphs having quadratic \(\sigma\)-polynomials.
Reviewer: U.Baumann

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] and , On chromatic equivalence of graphs. in Theory and Applications of Graphs. and , Eds., Springer-Verlag Lecture Notes in Mathematics, Vol. 642, Springer-Verlag, New York (1978). · Zbl 0369.05032
[2] Frucht, Ars Combinatoria 16-A pp 161– (1983)
[3] Korfhage, J. Combinatorial Theory, Series B 24 pp 137– (1978)
[4] and , Characterization of graphs having quadratic ??-polynomials, to appear.
[5] Read, J. Combinatorial Theory 4 pp 52– (1968) · Zbl 0165.32802
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.