zbMATH — the first resource for mathematics

On the chromatic uniqueness of the graph \(W(n,n-2,k)\). (English) Zbl 0857.05039
For integers \(n\geq 4\) and \(k\geq 1\), \(W(n,n-2,k)\) denotes a graph constructed in the following manner: Take a wheel \(W_n\) of order \(n\) (i.e. \(W_n\) consists of a cycle \(C\) of length \(n-1\) and a vertex \(v\) incident to all vertices of \(C\)), delete an edge between \(v\) and some vertex \(u\) of \(C\), and replace \(u\) by \(k\) independent vertices \(u_1,\dots,u_k\) such that the neighbourhood of each \(u_i\) consists of the two neighbours of \(u\) in \(C\). The authors prove that \(W(n,n-2,k)\) is chromatically unique for each even \(n\geq6\) and each \(k\geq1\), i.e. each graph having the same chromatic polynomial as \(W(n,n-2,k)\) is isomorphic to \(W(n,n-2,k)\).
Reviewer: A.Huck (Hannover)

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Chia, G.L.: The chromaticity of wheels with a missing spokes. Discrete Math.82, 209–212 (1990) · Zbl 0712.05025 · doi:10.1016/0012-365X(90)90326-D
[2] Dirac, G.A.: On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg,25, 71–76 (1967) · Zbl 0098.14703 · doi:10.1007/BF02992776
[3] Dong, F.M.: On the chromatic uniqueness of generalized wheel graphs, J. Mathematical Research and Exposition (in Chinese),10, 447–454 (1990) · Zbl 0774.05038
[4] Koh, K.M., Teo, K.L.: The search for chromatic unique graphs, Graphs and Combinatorics6, 259–285 (1990) · Zbl 0727.05023 · doi:10.1007/BF01787578
[5] Liu Yanpei, Graph Theory and Algorithm, (in Chinese), Chinese Academy of Sciences (1981)
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.