×

On properties of adjoint polynomials of graphs and their applications. (English) Zbl 1053.05055

Authors’ abstract: For a graph \(G\), we denote by \(P(G,\lambda)\) the chromatic polynomial of \(G\) and by \(h(G,x)\) the adjoint polynomial of \(G\). A graph \(G\) is said to be {chromatically unique} if for any graph \(H\), \(P(H,\lambda)=P(G,\lambda)\) implies \(H\cong G\). In this paper, we investigate some algebraic properties of the adjoint polynomials of some graphs. Using these properties, we obtain necessary and sufficient conditions for \(K_n-E(\bigcup_{a,b}T_{1,a,b})\) and \(\overline{(\bigcup_i C_{n_i})\cup(\bigcup_j D_{m_j})\cup(\bigcup_{a,b}T_{1,a,b})}\) to be chromatically unique if \(G_i\in\{C_n,D_n,T_{1,a,b}\mid n\geq5,3\leq a\leq10, a\leq b\}\) and \(h(P_m)\nmid h(G_i)\) for all \(m\geq2\). Moreover, many new chromatically unique graphs are given.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite