Chromatic uniqueness in a family of 2-connected graphs (Q1356689): Difference between revisions

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.