On the chromatic uniqueness of the graph \(W(n,n-2,k)\) (Q1923777): Difference between revisions

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)\).