On the chromatic uniqueness of the graph \(W(n,n-2,k)\) (Q1923777): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 15:59, 1 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the chromatic uniqueness of the graph \(W(n,n-2,k)\) |
scientific article |
Statements
On the chromatic uniqueness of the graph \(W(n,n-2,k)\) (English)
0 references
13 October 1996
0 references
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)\).
0 references
chromatic uniqueness
0 references
wheel
0 references
chromatic polynomial
0 references