zbMATH — the first resource for mathematics

The chromaticity of graphs \(K_ n(1,m)\). (Chinese. English summary) Zbl 0593.05028
The graphs under consideration are finite, undirected, simple graphs. Two graphs G and H are said to be chromatically equivalent if they have the same chromatic polynomial, i.e. \(M_ G(\lambda)=M_ H(\lambda)\). A graph G is said to be chromatically unique if \(M_ H(\lambda)=M_ G(\lambda)\) implies that H is isomorphic to G. C. Y. Chao and E. G. Whitehead jun. (1978, 1979), and B. Loerine (1978) had proved that some graphs are chromatically unique. In this paper, the following results are proved: Let \(K_ n(1,0)\) denote the graph obtained by subdividing an edge of a complete graph \(K_ n\) and let \(K_ n(1,m)\) denote the graph obtained by adding m edges (0\(\leq m\leq n-2)\) to \(K_ n(1,m)\) such that all these m edges are incident with the subdividing vertex. Then \(K_ n(1,m)\), \(0\leq m\leq n-2\), are chromatically unique if \(n\neq m+5\) or \(m+6\). For \(n=m+5\), there is only one graph which is chromatically equivalent to \(K_ n(1,m)\). For \(n=m+6\), there are four graphs which are chromatically equivalent to \(K_ n(1,m)\).
Reviewer: H.-P.Yap

05C15 Coloring of graphs and hypergraphs