Classification of chromatically unique graphs having quadratic \(\sigma\)- polynomials.

*(English)*Zbl 0686.05021Let 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.

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

##### MSC:

05C15 | Coloring of graphs and hypergraphs |

##### Keywords:

vertex colouring; quadratic sigma-polynomial; chromatic polynomial; Chromatically unique graphs
PDF
BibTeX
XML
Cite

\textit{N.-Z. Li} et al., J. Graph Theory 11, No. 2, 169--176 (1987; Zbl 0686.05021)

Full Text:
DOI

##### References:

[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.