On graphs in which any pair of colour classes but one induces a tree (Q1357722)

For \(m\geq 3\), let \({\mathcal F}_m\) be the family of graphs \(G\) that possesses an independent set partition \(\{A_1,\ldots,A_m\}\) such that the subgraphs of \(G\) induced by \(A_i\cup A_j\) are trees except one, which is a forest having two components. In this paper it is shown that for each \(G\) of order \(n\) in \({\mathcal F}_m\), \(t(G)\leq f(n,m)=\frac{1}{3}(3n-2m) {{m-1} \choose {2}}-m+2\), where \(t(G)\) denotes the number of triangles in \(G\). Let \(\rho(G)=f(n,m)-t(G)\). The graphs in \({\mathcal F}_m\) with \(\rho(G)=0\) and the graphs in \({\mathcal F}_3\) with \(\rho(G)=1\) are characterized. By applying the first characterization, it is deduced that a graph \(G\) of order \(n\geq m\) is in \({\mathcal F}_m\) with \(\rho(G)=0\) iff its chromatic polynomial is given by \(\lambda(\lambda-1)\cdots(\lambda-m+3)(\lambda-m+2)^2(\lambda-m+1)^{n-m}\). By applying the second characterization it is shown that the graphs obtained from the wheels of even order by deleting two consecutive spokes are uniquely determined by their chromatic polynomials, which solves partially Problem 4 in \textit{K. M. Koh} and \textit{K. L. Teo} [Graphs Comb. 5, No. 3, 259-285 (1990; Zbl 0727.05023)].