1 Introduction

In this paper, all graphs are simple and finite. Terminologies and notations not explained here can be found in Bondy and Murty [4].

For any graph G, let V(G), E(G), |V(G)| and |E(G)| denote the vertex set, edge set, order and size of G, respectively. For a positive integer k, a proper k-coloring, or simply a k-coloring of G, is a map \(\phi : V(G)\rightarrow \{1,2,\ldots ,k\}\) such that \(\phi (u)\ne \phi (v)\), if \(uv\in E(G)\). The chromatic number \(\chi (G)\) is the minimum k for which there exists a k-coloring of G. The chromatic polynomial of G, denoted by P(G, k), is the number of k-colorings of G. In 1912, Birkhoff [1] introduced the chromatic polynomial for planar graphs in an attempt to solve the Four Color Problem using tools from analysis. The chromatic polynomial was later defined and investigated for general graphs by Whitney [18].

Although the chromatic polynomial of a graph has been concerned by many scholars, we still know very little about it. In particular, finding a general bound remains a major challenge. The first result of this type, due to Birkhoff [2], is as follows:

$$\begin{aligned} P(G,x)\ge x(x-1)(x-2)(x-3)^{n-x} \end{aligned}$$

for any planar graph G of order n and any real number \(x\ge 5\). Birkhoff and Lewis [3] later conjectured this holds for all real number \(x\ge 4\). The case \(x=4\) is equivalent to the celebrated Four Color Theorem, which was resolved much later.

Let N and \(\mathcal {G}_{k}(n)\) denote the set of natural numbers and the family of all k-chromatic graphs of order n, respectively. In 1975, Tomescu [14] provided an upper bound for the chromatic polynomial as follows:

$$\begin{aligned} P(G,x)\le (x)_{k}x^{n-k} \end{aligned}$$

for any \(G\in \mathcal {G}_{k}(n)\) and any \(x\in N\), where \((x)_{k}=x(x-1)\cdots (x-k+1)\). Moreover, when \(x\ge k\), the bound is sharp if and only if \(G\cong K_{k}\cup (n-k)K_{1}\), and \(K_{k}\cap (n-k)K_{1}=\emptyset \) (the graph consisting of a k- clique plus \(n-k\) isolated vertices).

However, for the family of all connected k-chromatic graphs of order n, denoted by \(\mathcal {C}_{k}(n)\), the problem of finding a good upper bound for the chromatic polynomial of a graph in \(\mathcal {C}_{k}(n)\) becomes much more complicated.

Let \(\mathcal {C}^{*}_{k}(n)\) be the set of all graphs which are obtained from a k-clique by recursively attaching \(n-k\) leaves (adding \(n-k\) vertices of degree 1). In 1971, Tomescu proposed a conjecture as follows:

Conjecture 1

([12]) Let G be a graph in \(\mathcal {C}_{k}(n)\) where \(k\ge 4\). Then

$$\begin{aligned} P(G,k)\le k! (k-1)^{n-k}, \end{aligned}$$
(1)

and the equality holds if and only if \(G\in \mathcal {C}^{*}_{k}(n)\).

This conjecture has attracted the attention of many people. Tomescu first observed that if \(k=2\), inequality (1) holds as equality for any connected bipartite graph, whereas it is false for \(k=3\) when G is an odd cycle of length at least five. This shows that the condition \(k\ge 4\) is necessary. Partial results on this subject were obtained in [5, 7,8,9,10, 12,13,14]. Recently, Conjecture 1 is completely resolved by Fox et al. [11].

In 1990, Tomescu extended his original conjecture to a general number of colors:

Conjecture 2

([15]) If \(x\ge k\ge 4\), and G is a connected graph on n vertices with chromatic number k, then

$$\begin{aligned} P(G,x)\le (x)_{k} (x-1)^{n-k} \end{aligned}$$
(2)

with equality if and only if \(G\in \mathcal {C}^{*}_{k}(n)\).

In 2015, Brown and Erey proved the following two results on this conjecture:

Theorem 1

([5]) Let G be a graph in \(\mathcal {G}_{k}(n)\) having \(\triangle (G)=n-1\). Then for every \(x\in N\)

$$\begin{aligned} P(G,x)\le (x)_{k} (x-1)^{n-k}. \end{aligned}$$
(3)

Moreover for \(x\ge k\), the equality holds if and only if \(G\in \mathcal {C}^{*}_{k}(n)\).

Theorem 2

([5]) Let G be a graph in \(\mathcal {C}_{k}(n)\setminus \mathcal {C}^{*}_{k}(n)\) where \(k\ge 4\). Then

$$\begin{aligned} P(G,x)< (x)_{k} (x-1)^{n-k} \end{aligned}$$
(4)

for every real number x where \(x>n-2+\left( \left( {\begin{array}{c}n\\ 2\end{array}}\right) -\left( {\begin{array}{c}k\\ 2\end{array}}\right) -n+k \right) ^{2}\).

Although several authors have made some progress on Conjecture 2 (see, for example [5, 7,8,9,10, 16, 17]), it is still open.

In this paper, we are concerned with Conjecture 2. Let \(\mathcal {F}_{t}(n)\) and \(\mathcal {C}^{*}_{t}(n)\) denote the sets of all connected graphs on n vertices with clique number t and all graphs which are obtained from a t-clique by recursively attaching \(n-t\) leaves, respectively. In section 2, we shall show that if \(G\in \mathcal {F}_{t}(n) \backslash \mathcal {C}_{t}^{*}(n)\), then \(P(G,x)<(x-2)_{t-2}(x^{2}-2x+2)(x-1)^{n-t}\) for any integer \(x\ge \chi (G)\ge 4\). Furthermore, it is shown that Conjecture 2 holds under the condition that \(\omega (G)=\chi (G)=k\ge 4\). In addition, we also show that for any graph \(G \in \mathcal {C}_{k}(n)\) with \(\omega (G)=k-1\) and any integer \(x\ge k\ge 4\), if G has two cliques, one of which is a \((k-1)\)-clique and the other a t-clique \((t\ge 4)\), and they have at most \(t-2\) vertices in common with \(k-3(k-t+1)-(k-t)^{2}\ge 0\), then

$$\begin{aligned} P(G,x)\le (x)_{k}(x-1)^{n-k}. \end{aligned}$$

In Sect. 3, we shall show that Conjecture 2 holds under the conditions that \(\triangle (G)=n-2\), and \(\triangle (G)=n-3\) and there exists a cut-vertex that is not a vertex of maximum degree in G.

2 Clique Number and Chromatic Polynomial

Before stating our new results, we have to give a lemma used later.

Let \(G_{1}\) and \(G_{2}\) be two graphs, and any nonnegative integer r with \(r\le min\{\omega (G_{1}),\omega (G_{2})\}\), where \(\omega (H)\) is the clique number of a graph H. Choose a \(K_{r}\) from each \(G_{i}\ (i=1,2)\), and form a new graph G from the union of \(G_{1}\) and \(G_{2}\) by identifying the two chosen \(K_{r}\) in an arbitrary manner. Then we call G a \(K_{r}\)-gluing of \(G_{1}\) and \(G_{2}\) [6]. When \(r=1\), G is also called a vertex-gluing of \(G_{1}\) and \(G_{2}\).

Lemma 1

([19]) Let \(G_{1}\) and \(G_{2}\) be two graphs. If G is a \(K_{r}\)-gluing of \(G_{1}\) and \(G_{2}\), then

$$\begin{aligned} P(G,x)=\frac{P(G_{1},x)P(G_{2},x)}{P(K_{r},x)}. \end{aligned}$$
(5)

Let G be a connected graph of order n and \(\omega (G)=t\). If \(G\in \mathcal {C}_{t}^{*}(n)\), then one may find that \(P(G,x)=(x)_{t}(x-1)^{n-t}\) for any integer \(x\ge t\) by first coloring the clique of order t and then recursively coloring the remaining vertices. Otherwise, one may deduce the following new result immediately from the proof of Lemma 2.1 in [10]:

For any integer \(x\ge \chi (G)\ge 4\), if \(G\in \mathcal {F}_{t}(n) \backslash \mathcal {C}_{t}^{*}(n)\), then

$$\begin{aligned} P(G,x)< (x-2)_{t-2}(x^{2}-2x+2)(x-1)^{n-t}. \end{aligned}$$
(6)

Moreover, it is easy to see that for any \(G\in \mathcal {F}_{t}(n)\) and any integer \(x\ge \chi (G)\ge 4\),

$$\begin{aligned} P(G,x)\le (x)_{t}(x-1)^{n-t}, \end{aligned}$$
(7)

and the equality holds if and only if \(G\in \mathcal {C}^{*}_{t}(n)\).

Remark

For a graph \(G\in \mathcal {F}_{t}(n)\), it is clear that G has a connected spanning subgraph \(H\in \mathcal {C}^{*}_{t}(n)\). Thus \(P(G,x)\le P(H,x)=(x)_{t}(x-1)^{n-t}\) for any integer \(x\ge \chi (G)\ge 4\). But the necessary and sufficient conditions for the establishment of the equality still need to be proved.

For any connected graph G of order n, it is well known that \(\omega (G)\le \chi (G)\). When \(\omega (G)= \chi (G)\), we have the following result.

Corollary 1

([10]) Let G be a graph in \(\mathcal {C}_{k}(n)\) where \(k\ge 4\). If \( \omega (G)=k\), then for any integer \(x\ge k\),

$$\begin{aligned} P(G,x)\le (x)_{k}(x-1)^{n-k}. \end{aligned}$$

Moreover, the equality holds if and only if \(G\in \mathcal {C}^{*}_{k}(n)\).

By Corollary 1, for any connected graph G with \(\omega (G)=\chi (G)=k\ge 4\), it is easy to see that Conjecture 2 is true.

Theorem 3

Let G be a graph in \(\mathcal {C}_{k}(n)\) having \(\omega (G)=k-1\). For any integer \(x\ge k \ge 4\), if G has two cliques, one of which is a \((k-1)\)-clique and the other a t-clique \((t\ge 4)\), and they have at most \(t-2\) vertices in common with \(k-3(k-t+1)-(k-t)^{2}\ge 0\), then

$$\begin{aligned} P(G,x)\le (x)_{k}(x-1)^{n-k}. \end{aligned}$$
(8)

Proof

Let \(H_{1}\) and \(H_{2}\) be, respectively, a \((k-1)\)-clique and a t-clique of G \((t\ge 4)\) such that they have at most \(t-2\) vertices in common with \(k-3(k-t+1)-(k-t)^{2}\ge 0\). Suppose that \(G'\) is a minimally connected spanning subgraph of G that contains \(H_{1}\) and \(H_{2}\). We now divide into two cases to proceed the proof.

Case 1.   \(H_{1}\cap H_{2}=\emptyset \).

Assume that \(G'_{i}\) is a connected subgraph of \(G'\) containing \(H_{i}\) \((i=1,2)\) such that \(G'_{1}\cap G'_{2}=K_{1}\) and \(G'_{1}\cup G'_{2}=G'\). Obviously, \(G'_{1}\in \mathcal {C}_{k-1}^{*}(n_{1})\) and \(G'_{2}\in \mathcal {C}_{t}^{*}(n_{2})\), where \(n_{1}+n_{2}=n+1\). For any integer \(x\ge k\ge 4\), by Lemma 1 we have

$$\begin{aligned} P(G',x)&=\frac{P(G'_{1},x)P(G'_{2},x)}{x}\nonumber \\&=\frac{(x)_{k-1}(x-1)^{n_{1}-(k-1)}(x)_{t}(x-1)^{n_{2}-t}}{x}\nonumber \\&=\frac{(x)_{k-1}(x)_{t}(x-1)^{n-k-t+2}}{x}\nonumber \\&=\frac{(x)_{k}(x-1)^{n-k}(x-2)(x-3)\cdots (x-t+1)}{(x-1)^{t-3}(x-k+1)}. \end{aligned}$$
(9)

Observe that

$$\begin{aligned}&(x-1)(x-k+1)-(x-t+2)(x-t+1)\nonumber \\&\qquad =(2t-k-3)x+k+3t-t^{2}-3\nonumber \\&\qquad \ge (2t-k-3)k+k+3t-t^{2}-3\nonumber \\&\qquad =k-3(k-t+1)-(k-t)^{2}\ge 0, \end{aligned}$$
(10)

where the first inequality holds, as \(x\ge k\) and \(k-3(k-t+1)-(k-t)^{2}\ge 0\) implies that \(t>\frac{k+3}{2}\).

In addition, for \(2\le i\le t-3\), it is clear that \(x-i<x-1\). Combining this with (9) and (10), one may follow that

$$\begin{aligned} P(G',x)\le (x)_{k}(x-1)^{n-k}. \end{aligned}$$
(11)

As \(G'\) is a connected spanning subgraph of G, we have

$$\begin{aligned} P(G,x)\le P(G',x)\le (x)_{k}(x-1)^{n-k}. \end{aligned}$$
(12)

Case 2.   \(H_{1}\cap H_{2}=K_{r}\) (\(1\le r\le t-2\)).

Suppose that \(G'_{i}\) is a connected subgraph of \(G'\) containing \(H_{i}\) \((i=1,2)\) such that \(G'_{1}\cap G'_{2}=K_{r}\) and \(G'_{1}\cup G'_{2}=G'\). Obviously, \(G'_{1}\in \mathcal {C}_{k-1}^{*}(n_{1})\) and \(G'_{2}\in \mathcal {C}_{t}^{*}(n_{2})\), where \(n_{1}+n_{2}=n+r\). For any integer \(x\ge k\ge 4\), by Lemma 1 one may find that

$$\begin{aligned} P(G',x)&=\frac{P(G'_{1},x)P(G'_{2},x)}{P(K_{r},x)}\nonumber \\&=\frac{(x)_{k-1}(x-1)^{n_{1}-(k-1)}(x)_{t}(x-1)^{n_{2}-t}}{(x)_{r}}\nonumber \\&=\frac{(x)_{k-1}(x)_{t}(x-1)^{n+r-k-t+1}}{(x)_{r}}\nonumber \\&=\frac{(x)_{k}(x-1)^{n-k}(x-r)(x-r-1)\cdots (x-t+1)}{(x-1)^{t-r-1}(x-k+1)}. \end{aligned}$$
(13)

By (10), we have

$$\begin{aligned}&(x-1)(x-k+1)-(x-t+2)(x-t+1)\ge 0. \end{aligned}$$
(14)

Consider that \(x-r\le x-1\) and \(x-i<x-1\ (r+1\le i\le t-3)\). Combining this with (13) and (14), one may deduce that

$$\begin{aligned} P(G',x)\le (x)_{k}(x-1)^{n-k}. \end{aligned}$$
(15)

Since \(G'\) is a connected spanning subgraph of G, we have

$$\begin{aligned} P(G,x)\le P(G',x)\le (x)_{k}(x-1)^{n-k}. \end{aligned}$$
(16)

This completes the proof of the theorem. \(\square \)

As a consequence of Theorem 4, we have the following

Corollary 2

Let G be a graph in \(\mathcal {C}_{k}(n)\) having \(\omega (G)=k-1 \ (k\ge 7)\). For any integer \(x\ge k\ge 7\), if G has two \((k-1)\)-cliques with at most \(k-3\) vertices in common, then

$$\begin{aligned} P(G,x)\le (x)_{k}(x-1)^{n-k}. \end{aligned}$$
(17)

3 Maximum Degree and Chromatic Polynomial

Theorem 4

For any graph \(G\in \mathcal {C}_{k}(n)\) and any integer \(x\ge k\ge 4\), if \(\triangle (G)=n-2\), then

$$\begin{aligned} P(G,x)\le (x)_{k}(x-1)^{n-k} \end{aligned}$$
(18)

with equality if and only if \(G\in \mathcal {C}^{*}_{k}(n)\).

Proof

Assume that G is a graph in \(\mathcal {C}_{k}(n)\) with \(\triangle (G)=n-2\). Let \(u\in V(G)\) and \(d_{G}(u)=n-2\). Then there must exist a vertex v nonadjacent to u in G. Obviously, \(G-v\) is connected, and \(k-1\le \chi (G-v)\le k\). We first prove the following

Claim.   \(\chi (G-v)=k\).

Proof

If \(\chi (G-v)=k-1\), then \(G-v\) has a \((k-1)\)-coloring \(\phi \). We now color the vertex v with that of u, namely, \(\phi (v)=\phi (u)\). It leads to a \((k-1)\)-coloring of G, which contradicts \(\chi (G)=k\). Thus, \(\chi (G-v)=k\).      \(\Box \)

It is easy to see that \(d_{G-v}(u)=\triangle (G-v)=n-2\). By Theorem 1, for any integer \(x\ge k\ge 4\), we have

$$\begin{aligned} P(G-v,x)\le (x)_{k}(x-1)^{n-k-1}. \end{aligned}$$
(19)

Moreover, the equality holds if and only if \(G-v\in \mathcal {C}^{*}_{k}(n-1)\).

As G is connected, there must be a vertex \(w\in V(G-v)\) such that \(vw\in E(G)\). Let H denote the graph obtained from G by removing all edges incident with v except for vw. It is clear that H is a connected spanning subgraph of G. For any integer \(x\ge k\ge 4\), one may find that

$$\begin{aligned} P(H,x)=(x-1)P(G-v,x). \end{aligned}$$
(20)

Combining (19) with (20), we have

$$\begin{aligned} P(H,x)\le (x)_{k}(x-1)^{n-k}. \end{aligned}$$

Observe that \(P(G,x)\le P(H,x)\). It implies that \(P(G,x)\le (x)_{k}(x-1)^{n-k}\). Obviously, if \(G\in \mathcal {C}^{*}_{k}(n)\), the equality holds. On the other hand, if the equality holds, it means that \(P(H,x)=(x)_{k}(x-1)^{n-k}\) and \(G=H\). Note that \(P(H,x)=(x)_{k}(x-1)^{n-k}\) if and only if \(G-v\in \mathcal {C}^{*}_{k}(n-1)\) by Theorem 1. And it follows that the \(P(H,x)=(x)_{k}(x-1)^{n-k}\) if and only if \(H\in \mathcal {C}^{*}_{k}(n)\). Thus, the equality holds if and only if \(G\in \mathcal {C}^{*}_{k}(n)\), as desired. \(\square \)

Theorem 5

Let G be a graph in \(\mathcal {C}_{k}(n)\) with \(\triangle (G)=n-3\). For any integer \(x\ge k\ge 4\), if there exists a cut-vertex which is not a vertex of maximum degree in G, then

$$\begin{aligned} P(G,x)\le (x)_{k}(x-1)^{n-k} \end{aligned}$$

with equality if and only if \(G\in \mathcal {C}^{*}_{k}(n)\).

Proof

Let u be a vertex of degree \(n-3\) in G. Then there are two vertices nonadjacent to u in G, say v and w.

If the set \(\{v,w\}\) has a vertex, say v which is a cut-vertex of G, then \(G-v\) is disconnected. Thus, \(G-v\) has at least two components. Let \(N_{G}(u)=\{y_{1},y_{2},\ldots , y_{n-3}\}\) and \({N}_{G}[u]=N_{G}(u)\cup \{u\}\). Obviously, the induced subgraph \(G[{N}_{G}[u]]\) is connected. It implies that \(G-v\) has exactly two components, one of which is \(G[{N}_{G}[u]]\) and the other w. Therefore w is an isolated vertex in \(G-v\). It means that w is a vertex of degree 1 in G, and G can be obtained from the graph \(G-w\) by adding the vertex w and joining v to w. Thus, we have

$$\begin{aligned} P(G,x)=(x-1)P(G-w,x). \end{aligned}$$
(21)

It is clear that \(\chi (G-w)=\chi (G)=k\) and \(d_{G-w}(u)=\triangle (G-w)=n-3\). Observe that \(G-w\) is connected. For any integer \(x\ge k\ge 4\), by Theorem 5 we have

$$\begin{aligned} P(G-w,x)\le (x)_{k}(x-1)^{n-k-1}. \end{aligned}$$
(22)

And the equality holds iff \(G-w\in \mathcal {C}_{k}^{*}(n-1)\).

Combining (21) with (22). we obtain

$$\begin{aligned} P(G,x)\le (x)_{k}(x-1)^{n-k} \end{aligned}$$

with equality iff \(G\in \mathcal {C}_{k}^{*}(n)\).

Now suppose that neither v nor w are cut-vertices of G. Then there must be some vertex \(y_{i}\ (1\le i\le n-3)\) which is a cut-vertex of G. Since u is adjacent to \(y_{1},y_{2},\ldots ,y_{i-1},y_{i+1},\ldots \), \(y_{n-3}, G-y_{i}\) has at most three components. Let c(H) denote the number of components of a graph H. We now divide into two cases to complete the rest of proof.

Case 1.   \(c(G-y_{i})=3\).

It is clear that three components of \(G-y_{i}\) are \(G[{N}_{G}[u]-y_{i}], \ v\) and w. One may deduce that both v and w are vertices of degree 1 in G. Hence \(G=(G-v-w)+y_{i}v+y_{i}w\). And then it follows that

$$\begin{aligned} P(G,x)=(x-1)^{2}P(G-v-w,x). \end{aligned}$$
(23)

It is easy to see that \(\chi (G-v-w)=k\) and \(d_{G-v-w}(u)=\triangle (G-v-w)=n-3\). Note that \(G-v-w\) is also connected. For any integer \(x\ge k\ge 4\), by Theorem 1 we have

$$\begin{aligned} P(G-v-w,x)\le (x)_{k}(x-1)^{n-k-2}. \end{aligned}$$
(24)

Moreover, the equality holds iff \(G-v-w\in \mathcal {C}^{*}_{k}(n-2)\).

By (23) and (24), one may find that

$$\begin{aligned} P(G,x)\le (x)_{k}(x-1)^{n-k} \end{aligned}$$

with equality iff \(G\in \mathcal {C}_{k}^{*}(n)\).

Case 2.   \(c(G-y_{i})=2\).

We divide into the following two subcases.

Subcase 2.1.   \(G[{N}_{G}[u]-y_{i}]\) is a component of \(G-y_{i}\).

It is easy to see that the other component of \(G-y_{i}\) must be the edge vw. Since G is connected, there exists at least one vertex in \(\{v,w\}\) adjacent to \(y_{i}\).

If only one vertex in \(\{v,w\}\), say v is adjacent to \(y_{i}\), then v is a cut-vertex of G, a contradiction.

We now suppose that both v and w are adjacent to \(y_{i}\), then G is a vertex-gluing of \(G-v-w\) and the triangle \(C_{3}=y_{i}vwy_{i}\). Therefore we obtain

$$\begin{aligned} P(G,x)&=\frac{P(G-v-w,x)P(C_{3},x)}{x}\nonumber \\&=(x-1)(x-2)P(G-v-w,x). \end{aligned}$$
(25)

As in case 1, one may follow that

$$\begin{aligned} P(G-v-w,x)\le (x)_{k}(x-1)^{n-k-2}. \end{aligned}$$
(26)

Combining (25) with (26), we have

$$\begin{aligned} P(G,x)<(x)_{k}(x-1)^{n-k}. \end{aligned}$$

Subcase 2.2.   \(G[{N}_{G}[u]-y_{i}]\) is not a component of \(G-y_{i}\).

It is clear that there must be only one vertex in \(\{v,w\}\), say v such that \(G[({N}_{G}[u]-y_{i})\cup \{v\}]\) is a component of \(G-y_{i}\). It implies that w is the other component of \(G-y_{i}\). Thus, w is a vertex of degree 1 in G and G can be obtained from the graph \(G-w\) by adding the vertex w and joining \(y_{i}\) to w. Furthermore, one may find that

$$\begin{aligned} P(G,x)=(x-1)P(G-w,x). \end{aligned}$$
(27)

Obviously, \(\chi (G-w)=k\) and \(d_{G-w}(u)=\triangle (G-w)=n-3\). Observe that \(G-w\) is connected. By Theorem 5, we yield that

$$\begin{aligned} P(G-w,x)\le (x)_{k}(x-1)^{n-k-1} \end{aligned}$$
(28)

for any integer \(x\ge k\ge 4\), and equality holds if and only if \(G-w\in \mathcal {C}_{k}^{*}(n-1)\).

Combining (27) with (28), we have

$$\begin{aligned} P(G,x)\le (x)_{k}(x-1)^{n-k} \end{aligned}$$

with equality iff \(G\in \mathcal {C}_{k}^{*}(n)\). This completes the proof of Theorem 6. \(\square \)