Chromatic uniqueness in a family of 2-connected graphs (Q1356689): 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:27, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Chromatic uniqueness in a family of 2-connected graphs |
scientific article |
Statements
Chromatic uniqueness in a family of 2-connected graphs (English)
0 references
14 January 1998
0 references
Let \(P(G,\lambda)\) be the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are said to be chromatically equivalent if \(P(G,\lambda)= P(H,\lambda)\). A graph \(G\) is said to be chromatically unique, if there exists no graph \(H\), which is not isomorphic with \(G\), but \(G\) and \(H\) are chromatically equivalent. For integers \(n\geq 4\) and \(k\geq 1\), the graph \(F_{n,k}\) is defined as follows. Let \(H_n= P_{n-1}+ K_1\) be the join of a path \(P_{n-1}\) on \(n-1\) vertices with a vertex. Then \(H_n\) has exactly two vertices, say \(x\) and \(y\), each of degree 2. The graph \(F_{n,k}\) is obtained from \(H_n\) by adjoining \(k\) new vertices \(u_1,u_2,\dots,u_k\) and adding \(2k\) edges joining them to \(x\) and \(y\). The author proves that, for any odd integer \(n\geq 5\) and any integer \(k\geq 1\), \(F_{n,k}\) is chromatically unique. This gives a partial solution to Problem 5 given in \textit{K. M. Koh} and \textit{K. L. Teo} [The search for chromatically unique graphs, Graphs Comb. 6, No. 3, 259-285 (1990; Zbl 0727.05023)]. Reviewer's remark: K. L. Teo was misprinted as C. P. Teo in this paper.
0 references
chromatic polynomial
0 references
chromatically equivalent
0 references
chromatically unique
0 references