Independence Number and Maximal Chromatic Polynomials of Connected Graphs

Let \({\mathcal {C}}_{k}(n)\) ${\mathcal{C}}_k(n)$ denote the family of all connected graphs of order n with chromatic number k. In this paper we show that the conjecture proposed by Tomescu which if \(x\ge k\ge 4\) $x\ge k\ge 4$ and \(G\in {\mathcal {C}}_{k}(n)\) $G\in {\mathcal{C}}_k(n)$ , then \(\begin{aligned} P(G,x)\le (x)_{k} (x-1)^{n-k} \end{aligned}\) $$\begin{array}{c}\hfill P(G,x)\le {(x)}_k{(x-1)}^{n-k}\end{array}$$ holds under the additional condition that G has an independent cut-set T of size at most 2 such that the number of components in \(G{\setminus } T\) $G\backslash T$ is equal to the independence number of G.