1 Introduction

In this paper, all graphs are finite and simple. Throughout this paper, n and m will always denote, respectively, the number of vertices and the number of edges in a graph G. The readers are assumed familiar with graph theory terminology as in Bondy and Murty [2], for example.

For any graph G, let V(G), E(G) and v(G) be the vertex set, edge set and order of G, respectively. For a positive integer \(\lambda\), a proper \(\lambda\)-coloring, or simply a \(\lambda\)-colorings of G is a map \(\phi : V(G)\rightarrow \{1,2,\ldots ,\lambda \}\) such that \(\phi (u)\ne \phi (v)\) where u and v are adjacent vertices. The chromatic polynomial of G, denoted by \(P(G,\lambda )\), is the number of \(\lambda\)-colorings of G. For any positive integer k, let \(\alpha (G,k)\) denote the number of partitions of V(G) into exactly k non-empty independent sets. Then

$$\begin{aligned} P(G,\lambda )=\sum ^{n}_{k=1}\alpha (G,k)(\lambda )_{k}, \end{aligned}$$
(1)

where \((\lambda )_{k}=\lambda (\lambda -1)\ldots (\lambda -k+1)\) and \(n=v(G)\).

Let G be a graph of order n. It is obvious that there exist n-colorings of G. For any n-coloring \(\Gamma\) of G, let \(l(\Gamma )\) be the actual number of colors used. The mean color number \(\mu (G)\) of G, defined by Bartels and Welsh [1], is the average of \(l(\Gamma )\)’s over all n- colorings \(\Gamma\). The number of n-colorings \(\Gamma\) of G with \(l(\Gamma )=k\) is \(\alpha (G,k)(n)_{k}\). Therefore by the definition of \(\mu (G)\), we have

$$\begin{aligned} \mu (G)=\frac{\sum _{k=1}^{n}k(n)_{k}\alpha (G,k)}{\sum _{k=1}^{n}(n)_{k}\alpha (G,k)}. \end{aligned}$$

Bartels and Welsh also presented an expression of \(\mu (G)\) in terms of the chromatic polynomials.

Theorem 1.1

([1])   If \(v(G)=n\), then

$$\begin{aligned} \mu (G)=n\left( 1-\frac{P(G,n-1)}{P(G,n)}\right) . \end{aligned}$$
(2)

Theorem 1.1 shows that \(\mu (G)\le n\) where equality holds iff G is complete. For the empty graph \(O_{n}\) of order n, we have

$$\begin{aligned} \mu (O_{n})=n\left( 1-\left( 1-\frac{1}{n}\right) ^{n}\right) . \end{aligned}$$

Bartels and Welsh conjectured that \(\mu (O_{n})\) is a lower bound of \(\mu (G)\) for any graph G of order n, and their conjecture was proved by Dong [4]. They also proposed a more general conjecture that if H is a spanning subgraph of G, then \(\mu (G)\ge \mu (H)\). But counterexamples have been discovered by Mosca [8].

Thus, in general the following equality is not true:

$$\begin{aligned} \mu (G)\ge \mu (H), \end{aligned}$$
(3)

where H is a subgraph of G. But it is true for some special cases. It is clear that (3) holds if G is complete. And Dong proved that (3) holds if H is a spanning subgraph of G and H is either a tree or an empty graph [4]. Several years later, he also proved that \(\mu (G)\ge \mu (H)\) if G is a chordal graph and H is a spanning subgraph of G, and the equality holds iff \(H\cong G\) [5].

In this paper, we are concerned with two conjectures proposed by Dong. The first is the following:

Conjecture 1

([5])   For any graph G and a vertex w in G with \(d(w)\ge 1\), if H is a graph obtained from G by deleting all but one of the edges which are incident to w, then \(\mu (G)\ge \mu (H)\).

In Sect. 2 we shall show that Conjecture 1 holds under the condition that w is a simplicial vertex in G with \(d(w)\ge 1\). And Conjecture 1 also holds for the wheel of order n.

The second conjecture is as follows:

Conjecture 2

([5])   For any graph G and a vertex w in G, \(\mu (G)\ge \mu ((G-w)\cup K_{1})\).

In Sect. 3 we shall show that Conjecture 2 also holds under the condition that w is a simplicial vertex in G. And when G is a connected (n, m)-graph and w is not a cut vertex in G with \(d(w)=n-1\), if \(m\le (\frac{\sqrt{2}}{2}+2)n-4.5-\sqrt{2}\), then \(\mu (G)\ge \mu ((G-w) \cup K_{1})\). For the wheel of order n, conjecture 2 holds too.

For some special cases, for example, chordal graph and 2-tree, the two conjectures are true [5].

2 The First Conjecture

For any graphs G, H and for any real \(\lambda\), define

$$\begin{aligned} \tau (G,H,\lambda )=P(G,\lambda )P(H,\lambda -1)-P(G,\lambda -1)P(H,\lambda ). \end{aligned}$$
(4)

By Theorem 1.1, one may deduce that

Lemma 2.1

([5])   For any graphs G and H with \(v(G)=v(H)=n\), the inequality \(\mu (G)\ge \mu (H)\) is equivalent to \(\tau (G,H,n)\ge 0\).

Now we present a well known result on chromatic polynomial used in this paper.

Lemma 2.2

([9])   For any graph G, if \(\lambda \ge v(G)-1\), then \(P(G,\lambda )\ge 0\) where equality holds iff G is complete and \(\lambda =v(G)-1\).

For any vertex x in G, let \(N_{G}(x)\) (or simply N(x)) denote the set of vertices in G which are adjacent to x, and let \(d_{G}(x)\) (or simply d(x)) be the degree of x in G. The vertex x in G is called a simplicial vertex if either \(d(x)=0\) or G[N(x)] is a clique.

Theorem 2.1

For any graph G of order n and a simplicial vertex w in G with \(d(w)\ge 1\), if \(\lambda \ge n-1\) and H is a graph obtained from G by deleting all but one of the edges which are incident to w, then \(\tau (G,H,\lambda ) \ge 0\) where equality holds iff \(d(w)=1\) or \(\lambda =n-1\) and \(G-w\) is complete.

Proof

Let \(G^{*}=G-w\). For any positive integer \(\lambda \ge d\), since w is a simplicial vertex in G, we have

$$\begin{aligned} P(G,\lambda )=(\lambda -d)P\left( G^{*},\lambda \right) ,\ \ \ P(H,\lambda )=(\lambda -1)P\left( G^{*},\lambda \right) , \end{aligned}$$
(5)

where \(d=d(w)\).

Thus, by (5) and the definition of \(\tau (G,H,\lambda )\), it follows that

$$\begin{aligned} \tau (G,H,\lambda )=&(\lambda -d)P\left( G^{*},\lambda \right) (\lambda -2)P\left( {G^{*}},\lambda -1\right) \nonumber \\&-(\lambda -d-1)P\left( G^{*},\lambda -1\right) (\lambda -1)P\left( G^{*},\lambda \right) \nonumber \\ =&(d-1)P\left( G^{*},\lambda \right) P\left( {G^{*}},\lambda -1\right) . \end{aligned}$$
(6)

In addition, for \(\lambda \ge n-1\), by Lemma 2.2, we get

$$\begin{aligned} P\left( G^{*},\lambda \right) >0,\ \ \ P\left( G^{*},\lambda -1\right) \ge 0. \end{aligned}$$
(7)

Observe that \(d(w)\ge 1\). Therefore (6) and (7) imply the theorem holds. □

By Theorem 2.1 and Lemma 2.1, we have the first result on mean color number.

Theorem 2.2

For any graph G and a simplicial vertex w in G with \(d(w)\ge 1\), if H is a graph obtained from G by deleting all but one of the edges which are incident to w, then \(\mu (G)\ge \mu (H)\), where equality holds iff \(d(w)=1\).

Now let us show that Conjecture 1 holds for the wheel of order n: for that let us introduce some general results.

Lemma 2.3

Let G be a graph of order n, let \(w\in V(G)\) with \(d(w)=n-1\), and let us write \(G^{*}=G-w\). If H is a graph obtained from G by deleting all but one of the edges which are incident to w, then \(\tau (G,H,\lambda ) \ge 0\) is equivalent to \(\lambda (\lambda -2)(P(G^{*},\lambda -1))^{2}\ge (\lambda -1)^{2}P(G^{*},\lambda )P(G^{*},\lambda -2)\).

Proof

By the definition of \(\tau (G,H,\lambda )\), we have

$$\begin{aligned} \tau (G,H,\lambda )=P(G,\lambda )P(H,\lambda -1)-P(G,\lambda -1)P(H,\lambda ). \end{aligned}$$
(8)

By the equality \(d(w)=n-1\), one has that

$$\begin{aligned} P(G,\lambda )=\lambda P\left( G^{*},\lambda -1\right) . \end{aligned}$$
(9)

And it is evident that

$$\begin{aligned} P(H,\lambda )=(\lambda -1)P\left( G^{*},\lambda \right) . \end{aligned}$$
(10)

Combining (9) and (10) with (8), one may find that

$$\begin{aligned} \tau (G,H,\lambda )=\lambda (\lambda -2)\left( P\left( G^{*},\lambda -1\right) \right) ^{2} -(\lambda -1)^{2}P\left( G^{*},\lambda \right) P\left( G^{*},\lambda -2\right) . \end{aligned}$$
(11)

Hence \(\tau (G,H,\lambda )\ge 0\) iff \(\lambda (\lambda -2)(P(G^{*},\lambda -1))^{2}\ge (\lambda -1)^{2}P(G^{*},\lambda )P(G^{*},\lambda -2)\). This completes the proof of the theorem. □

By Lemma 2.3 and Lemma 2.1, we have the following

Corollary 2.1

Let G be a graph of order \(n\ (n\ge 2)\) and let \(w\in V(G)\) with \(d(w)=n-1\). If H is a graph obtained from G by deleting all but one of the edges which are incident to w, then \(\mu (G)\ge \mu (H)\) iff \(n(n-2)(P(G^{*},n-1))^{2}\ge (n-1)^{2}P(G^{*},n)P(G^{*},n-2)\), where \(G^{*}=G-w\).

Remark 1

In the early 1970’s Welsh and later, independently, Brenti [3] proposed a conjecture that for all \(\lambda \in N\) and all graphs G, \((P(G,\lambda ))^{2}\ge P(G,\lambda +1)P(G,\lambda -1)\). But a counterexample was found by Seymour [10]. Although in general the conjecture is not true, Dong et al. [6] proposed another conjecture as follows :

Let G be a graph of order n. For \(\lambda \in \mathbb {R}\) with \(\lambda \ge n-1\),

$$\begin{aligned} \left( P\left( G,\lambda \right) \right) ^{2}\ge P(G,\lambda +1)P(G,\lambda -1). \end{aligned}$$

This conjecture remains open. Obviously, Corollary 2.1 is closely related to it. If this conjecture is not true, then \(\mu (G)<\mu (H)\). And this leads to Conjecture 1 not being established.

The wheel of order n, denoted by \(W_{n}\), is defined as \(W_{n}=C_{n-1}+K_{1}\) (\(W_{n}\) is the join of \(C_{n-1}\) and \(K_{1}\)). For any vertex x in \(W_{n}\ (n\ge 4)\), it is clear that \(d(x)\ge 3\). The following result shows that Conjecture 1 is true for \(W_{n}\).

Theorem 2.3

For any wheel graph \(W_{n}\ (n\ge 4)\) and a vertex w in \(W_{n}\), if H is a graph obtained from \(W_{n}\) by deleting all but one of the edges which are incident to w, then \(\mu (W_{n})\ge \mu (H)\).

Proof

Let \(W_{n}\) be the wheel of order \(n \ (n\ge 4)\) and w be a vertex in \(W_{n}\). Now assume that H is a graph obtained from \(W_{n}\) by deleting all but one of the edges which are incident to w. The vertex w may be divided into the following two cases.

Case 1.   \(d(w)=n-1\), namely, w lies in the center of \(W_{n}\).

Let us write \(W_{n}^{*}=W_{n}-w\). By Corollary 2.1, we only need to check that \(n(n-2)(P(W_{n}^{*},n-1))^{2}-(n-1)^{2}P(W_{n}^{*},n)P(W_{n}^{*},n-2)\ge 0\).

According to the definition of chromatic polynomial of a graph, we have

$$\begin{aligned} P\left( W_{n}^{*},\lambda \right) =P\left( C_{n-1},\lambda \right) =(\lambda -1)^{n-1}+(-1)^{n-1}(\lambda -1). \end{aligned}$$

Thus,

$$\begin{aligned}&n(n-2)\left( P\left( W_{n}^{*},n-1\right) \right) ^{2}-(n-1)^{2}P\left( W_{n}^{*},n\right) P\left( W_{n}^{*},n-2\right) \nonumber \\&\quad =n(n-2)\left[ (n-2)^{n-1}+(-1)^{n-1}(n-2)\right] ^{2}-(n-1)^{2}\left[ (n-1)^{n-1} +(-1)^{n-1}(n-1)\right] \nonumber \\&\qquad \times \left[ (n-3)^{n-1}+(-1)^{n-1}(n-3)\right] . \end{aligned}$$
(12)

By the parity of n, we divide into the following two subcases.

Case 1.1. n is even.

By (12), it is easy to verify that \(n(n-2)(P(W_{n}^{*},n-1))^{2}-(n-1)^{2}P(W_{n}^{*},n)P(W_{n}^{*},n-2)>0\) for \(n=4\).

Now suppose that \(n\ge 6\).

By (12) we have

$$\begin{aligned}&n(n-2)\left( P\left( W_{n}^{*},n-1\right) \right) ^{2}-(n-1)^{2}P\left( W_{n}^{*},n\right) P\left( W_{n}^{*},n-2\right) \\&\quad =n(n-2)\left[ (n-2)^{n-1}-(n-2)\right] ^{2}-(n-1)^{2}\left[ (n-1)^{n-1}-(n-1)\right] \\&\qquad \times \left[ (n-3)^{n-1}-(n-3)\right] \\&\quad =n(n-2)(n-2)^{2(n-1)}-2n(n-2)^{n+1}-(n-1)^{2}\left[ (n-1)(n-3)\right] ^{n-1}\\&\qquad +(n-3)(n-1)^{n+1}+(n-1)^{3}(n-3)^{n-1}+2n-3\\&\quad =n(n-2)\left[ (n-1)(n-3)+1\right] ^{n-1}-2n(n-2)^{n+1}-(n-1)^{2}\left[ (n-1)(n-3)\right] ^{n-1}\\&\qquad +(n-3)(n-1)^{n+1}+(n-1)^{3}(n-3)^{n-1}+2n-3\\&\quad>(n-1)^{n}(n-3)^{n-1}-2n(n-2)^{n+1}+(n-3)(n-1)^{n+1}\\&\quad>(n-1)^{n}(n-3)^{n-1}-2n(n-2)^{n+1}+(n-3)(2n+1)(n-2)^{n}\\&\quad>(n-2)^{n}(n-3)^{n-1}-(n+3)(n-2)^{n}\\&\quad>2(n-3)^{2}(n-2)^{n}-(n+3)(n-2)^{n}=(n-2)^{n}\left( 2n^{2}-13n+15\right) >0, \end{aligned}$$

where the second inequality holds, as

$$\begin{aligned} (n-1)^{n+1}&=(n-2)^{n+1}+\left( {\begin{array}{c}n+1\\ 1\end{array}}\right) (n-2)^{n}+\left( {\begin{array}{c}n+1\\ 2\end{array}}\right) (n-2)^{n-1}+\cdots \\&>(n-2)^{n+1}+(n+1)(n-2)^{n}+2(n-2)^{n}. \end{aligned}$$

Case 1.2. n is odd.

By (12) we obtain

$$\begin{aligned}&n(n-2)\left( P\left( W_{n}^{*},n-1\right) \right) ^{2}-(n-1)^{2}P\left( W_{n}^{*},n\right) P\left( W_{n}^{*},n-2\right) \\&\quad =n(n-2)\left[ (n-2)^{n-1}+(n-2)\right] ^{2}-(n-1)^{2}\left[ (n-1)^{n-1}+(n-1)\right] \\&\qquad \times \left[ (n-3)^{n-1}+(n-3)\right] \\&\quad =n(n-2)(n-2)^{2(n-1)}+2n(n-2)^{n+1}-(n-1)^{2}\left[ (n-1)(n-3)\right] ^{n-1}\\&\qquad -(n-3)(n-1)^{n+1}-(n-1)^{3}(n-3)^{n-1}+2n-3\\&\quad>n(n-2)\left[ (n-1)(n-3)+1\right] ^{n-1}+4n(n-3)^{n+1}-(n-1)^{2}\left[ (n-1)(n-3)\right] ^{n-1}\\&\qquad -(n-3)(n-1)^{n+1}-(n-1)^{3}(n-3)^{n-1}\\&\quad>n(n-2)\left[ (n-1)(n-3)+1\right] ^{n-1}+\left[ 4(n-3)^{2}-(n-1)^{2}\right] (n-1)(n-3)^{n-1}\\&\qquad -(n-1)^{2}\left[ (n-1)(n-3)\right] ^{n-1}-(n-3)(n-1)^{n+1}\\&\quad>n(n-2)(n-1)^{n-1}(n-3)^{n-2}-\left[ (n-1)(n-3)\right] ^{n-1}-(n-3)(n-1)^{n+1}\\&\quad>(n-1)^{n}(n-3)^{n-1}-(n-3)(n-1)^{n+1}=(n-1)^{n}(n-3)\left[ (n-3)^{n-2}-(n-1)\right] \\&\quad >(n-1)^{n}(n-3)\left[ (n-3)^{2}-(n-1)\right] =(n-1)^{n}(n-3)\left( n^{2}-7n+10\right) \ge 0, \end{aligned}$$

where the third inequality holds, as

$$\begin{aligned} {}\left[ (n-1)(n-3)+1\right] ^{n-1}&=\left[ (n-1)(n-3)\right] ^{n-1}+\left( {\begin{array}{c}n-1\\ 1\end{array}}\right) \left[ (n-1)(n-3)\right] ^{n-2}+\cdots \\&>\left[ (n-1)(n-3)\right] ^{n-1}+(n-1)^{n-1}(n-3)^{n-2} \end{aligned}$$

and \(4(n-3)^{2}-(n-1)^{2}=3n^{2}-22n+35\ge 0\).

Case 2.   \(d(w)=3\), namely, w lies in the rim of \(W_{n}\).

Since \(d(w)=3\), it follows that

$$\begin{aligned} P(H,\lambda )=(\lambda -1) P\left( W_{n}-w,\lambda \right) =\lambda (\lambda -1)^{2}(\lambda -2)^{n-3}. \end{aligned}$$
(13)

And it is clear that

$$\begin{aligned} P\left( W_{n},\lambda \right) =\lambda P\left( C_{n-1},\lambda -1\right) =\lambda \left[ (\lambda -2)^{n-1}+(-1)^{n-1}(\lambda -2)\right] . \end{aligned}$$
(14)

Thus, by (4), (13) and (14), we have

$$\begin{aligned} \tau \left( W_{n},H,\lambda \right) =&P\left( W_{n},\lambda \right) P(H,\lambda -1)-P\left( W_{n},\lambda -1\right) P(H,\lambda )\nonumber \\ =&\lambda (\lambda -1)(\lambda -2)^{2}(\lambda -3)^{n-3}\left[ (\lambda -2)^{n-1} +(-1)^{n-1}(\lambda -2)\right] \nonumber \\&-\lambda (\lambda -1)^{3}(\lambda -2)^{n-3}\left[ (\lambda -3)^{n-1}+(-1)^{n-1}(\lambda -3)\right] . \end{aligned}$$
(15)

According to the parity of n, we can divide into the following two subcases.

Case 2.1.    n is even.

By (15) we get

$$\begin{aligned} \tau \left( W_{n},H,n\right) =&n(n-1)(n-2)^{2}(n-3)^{n-3}\left[ (n-2)^{n-1}-(n-2)\right] \\&-n(n-1)^{3}(n-2)^{n-3}\left[ (n-3)^{n-1}-(n-3)\right] \\ =&n(n-1)(n-2)^{n-3}(n-3)^{n-3}\left[ (n-2)^{4}-(n-1)^{2}(n-3)^{2}\right] \\&-n(n-1)(n-2)^{3}(n-3)^{n-3}+n(n-3)(n-1)^{3}(n-2)^{n-3}\\ =&n(n-1)(n-2)^{n-3}(n-3)^{n-3}\left( 2n^{2}-8n+7\right) \\&-n(n-1)(n-2)^{3}(n-3)^{n-3}+n(n-3)(n-1)^{3}(n-2)^{n-3}\\ \ge&n(n-1)(n-2)(n-3)^{n-3}\left( 2n^{2}-8n+7\right) \\&-n(n-1)(n-2)^{3}(n-3)^{n-3}+n(n-3)(n-1)^{3}(n-2)^{n-3}\\ =&n(n-1)(n-2)(n-3)^{n-3}\left( n^{2}-4n+3\right) +n(n-3)(n-1)^{3}(n-2)^{n-3}\\&>0. \end{aligned}$$

Case 2.2.   n is odd.

By (15) we have

$$\begin{aligned} \tau \left( W_{n},H,n\right) =&n(n-1)(n-2)^{2}(n-3)^{n-3}\left[ (n-2)^{n-1}+(n-2)\right] \\&-n(n-1)^{3}(n-2)^{n-3}\left[ (n-3)^{n-1}+(n-3)\right] \\ =&n(n-1)(n-2)^{n-3}(n-3)^{n-3}\left[ (n-2)^{4}-(n-1)^{2}(n-3)^{2}\right] \\&+n(n-1)(n-2)^{3}(n-3)^{n-3}-n(n-3)(n-1)^{3}(n-2)^{n-3}\\ =&n(n-1)(n-2)^{n-3}(n-3)^{n-3}\left( 2n^{2}-8n+7\right) \\&+n(n-1)(n-2)^{3}(n-3)^{n-3}-n(n-3)(n-1)^{3}(n-2)^{n-3}\\>&n(n-1)(n-3)(n-2)^{n-3}\left( 2n^{2}-8n+7\right) \\&+n(n-1)(n-2)^{3}(n-3)^{n-3}-n(n-3)(n-1)^{3}(n-2)^{n-3}\\ =&n(n-1)(n-3)(n-2)^{n-3}\left( n^{2}-6n+6\right) +n(n-1)(n-2)^{3}(n-3)^{n-3}\\ >&0. \end{aligned}$$

Thus, for \(d(w)=3\), by Lemma 2.1, we have

$$\begin{aligned} \mu (W_{n})>\mu (H). \end{aligned}$$

This completes the proof of the theorem. □

3 The Second Conjecture

For two disjoint graphs G and H, let \(G\cup H\) denote the graph with vertex set \(V(G)\cup V(H)\) and edge set \(E(G)\cup E(H)\). For any graph H and positive integer m, let \(H\cup mK_{1}\) be the graph obtained from H by adding m new vertices and no new edges.

Now we present the first result of this section.

Theorem 3.1

For any graph G and a simplicial vertex w in G, \(\mu (G)\ge \mu ((G-w)\cup K_{1})\).

Proof

If \(d(w)=0\), it is clear that the inequality holds.

Now assume that \(d(w)\ge 1\). As w is a simplicial vertex in G, we have

$$\begin{aligned} P(G,\lambda )=\left( \lambda -d(w)\right) P\left( G-w,\lambda \right) . \end{aligned}$$
(16)

Let \(H=(G-w)\cup K_{1}\). Then

$$\begin{aligned} P(H,\lambda )=\lambda P\left( G-w,\lambda \right) . \end{aligned}$$
(17)

For \(\lambda \ge n-1\), by (4), (16) and (17), one has that

$$\begin{aligned} \tau \left( G,H,\lambda \right)&=(\lambda -1)\left( \lambda -d(w)\right) P\left( G-w,\lambda \right) P\left( G-w,\lambda -1\right) \\&\quad -\lambda \left( \lambda -d(w)-1\right) P\left( G-w,\lambda \right) P\left( G-w,\lambda -1\right) \\&=d(w)P\left( G-w,\lambda \right) P\left( G-w,\lambda -1\right) \ge 0. \end{aligned}$$

Thus, by Lemma 2.1, \(\mu (G)\ge \mu (H)=\mu ((G-w)\cup K_{1})\).      □

By the proof of Theorem 3.1, one may find that if w is a simplicial vertex in G with \(d(w)\ge 1\) then \(\mu (G)>\mu ((G-w)\cup K_{1})\).

Corollary 3.1

Let G be a graph and w be a simplicial vertex in G with \(d(w)\ge 1\). If H is a subgraph of G which is obtained from G by deleting all edges adjacent to w. Then \(\mu (G)>\mu (H)\).

Proof

Let H be a subgraph of G which is obtained from G by deleting all edges adjacent to w. It is obvious that H is a spanning subgraph of G and \(H\cong (G-w)\cup K_{1}\). By the discussion above, this corollary follows immediately.       □

On the basis of Theorem 3.1, we can obtain a more general result as follows:

Corollary 3.2

Let G be any graph and \(w_{1},w_{2},\ldots ,w_{l}\) be all simplicial vertices in G. Then \(\mu (G)\ge \mu ((G-\cup ^{t}_{i=1} w_{i})\cup tK_{1}) \ (1\le t\le l)\).

Proof

As \(w_{t}\ (2\le t\le l)\) is a simplicial vertex in G, \(w_{t}\) is a simplicial vertex in \((G-\cup ^{t-1}_{i=1} w_{i})\). Moreover, it is also a simplicial vertex in \((G-\cup ^{t-1}_{i=1} w_{i})\cup (t-1)K_{1}\).

By Theorem 3.1, we have \(\mu ((G-\cup ^{t-1}_{i=1} w_{i}) \cup (t-1)K_{1})\ge \mu (G-w_{t}-\cup ^{t-1}_{i=1} w_{i})\cup (t-1)K_{1}\cup K_{1})=\mu ((G-\cup ^{t}_{i=1} w_{i})\cup tK_{1})\). It follows that \(\mu ((G-w_{1})\cup K_{1})\ge \mu ((G-(w_{1}\cup w_{2}))\cup 2K_{1})\ge \cdots \ge \mu ((G-\cup ^{t}_{i=1} w_{i})\cup tK_{1})\). Observe that \(w_{1}\) is a simplicial vertex in G too, by Theorem 3.1, we have \(\mu (G)\ge \mu ((G-w_{1})\cup K_{1})\). This implies the theorem holds. □

Similarly, we have the following

Corollary 3.3

Let G be any graph and \(w_{1},w_{2},\ldots ,w_{s}\) be all simplicial vertices in G with \(d(w_{i})\ge 1 \ (1\le i\le s)\). If \(H_{j}\ (1\le j\le s)\) is a subgraph of G which is obtained from G by sequentially deleting all edges adjacent to \(w_{i}\ (1\le i\le j)\), then \(\mu (G)>\mu (H_{j})\).

Theorem 3.2

Let G be a graph of order \(n\ (n\ge 2)\) and \(w\in V(G)\) with \(d(w)=n-1\). Assume that \(H=(G-w)\cup K_{1}\) and write \(G^{*}=G-w\). Then for \(\lambda \ge 1, \tau (G,H,\lambda )\ge 0\) iff \((P(G^{*},\lambda -1))^{2}\ge P(G^{*},\lambda ) P(G^{*},\lambda -2)\).

Proof

By the definition of \(\tau (G,H,\lambda )\), we have

$$\begin{aligned} \tau (G,H,\lambda )=P(G,\lambda )P(H,\lambda -1)-P(G,\lambda -1)P(H,\lambda ). \end{aligned}$$
(18)

Since \(d(w)=n-1\), one may deduce that

$$\begin{aligned} P(G,\lambda )=\lambda P\left( G^{*},\lambda -1\right) . \end{aligned}$$
(19)

And it is clear that

$$\begin{aligned} P(H,\lambda )=\lambda P\left( G^{*},\lambda \right) . \end{aligned}$$
(20)

By substituting (19) and (20) into (18), one may find that

$$\begin{aligned} \tau (G,H,\lambda )=\lambda (\lambda -1)\left[ \left( P\left( G^{*},\lambda -1\right) \right) ^{2}-P\left( G^{*},\lambda \right) P\left( G^{*},\lambda -2\right) \right] . \end{aligned}$$

Thus, for \(\lambda \ge 1\), \(\tau (G,H,\lambda )\ge 0\) iff \((P(G^{*},\lambda -1))^{2}-P(G^{*}, \lambda )P(G^{*},\lambda -2)\ge 0\), namely, \((P(G^{*},\lambda -1))^{2}\ge P(G^{*},\lambda )P(G^{*},\lambda -2)\). This completes the proof of the theorem. □

By Theorem 3.2 and Lemma 2.1, we get another result on mean color numbers.

Theorem 3.3

Let G be a graph of order \(n \ (n\ge 2)\), \(w\in V(G)\) with \(d(w)=n-1\) and \(G^{*}=G-w\). Then \(\mu (G)\ge \mu ((G-w)\cup K_{1})\) iff \((P(G^{*},n-1))^{2}\ge P(G^{*},n)P(G^{*},n-2)\).

Remark 2

It is evident that Theorem 3.3 is also related to Dong’s conjecture in Remark 1. Thus, if the conjecture is true, then \(\mu (G)\ge \mu ((G-w)\cup K_{1})\); otherwise, \(\mu (G)< \mu ((G-w)\cup K_{1})\). This leads to Conjecture 2 not being established.

In what follows we introduce an known inequality on chromatic polynomials of graphs.

Lemma 3.1

([7])   Let G be a connected (n, m)-graph. If \(\lambda \in \mathbb {R}\) and \(\lambda \ge \max \{n-1,\sqrt{2}(m-n+2.5)\}\), then

$$\begin{aligned} \left( P\left( G,\lambda \right) \right) ^{2}\ge P\left( G,\lambda +1\right) P\left( G,\lambda -1\right) . \end{aligned}$$
(21)

Theorem 3.4

Suppose that G is a connected (n, m)-graph and that w is a vertex such that \(d(w)=n-1\) and w is not a cut vertex of G. If \(m\le (\frac{\sqrt{2}}{2}+2)n-4.5-\sqrt{2}\), then

$$\begin{aligned} \mu (G)\ge \mu \left( (G-w)\cup K_{1}\right) . \end{aligned}$$
(22)

Proof

Let \(G^{*}=G-w\). As G is a connected graph and w is not a cut vertex in G, \(G^{*}\) is a connected graph too. It is clear that \(\mid V(G^{*})\mid =n-1\) and \(\mid E(G^{*})\mid =m-n+1\). Hence \(G^{*}\) is a connected \((n-1,m-n+1)\)-graph.

By the inequality \(m\le (\frac{\sqrt{2}}{2}+2)n-4.5-\sqrt{2}\), we have

$$\begin{aligned} (n-1)-1=n-2\ge \sqrt{2}(m-2n+4.5)=\sqrt{2}[(m-n+1)-(n-1)+2.5]. \end{aligned}$$
(23)

Then, by (23) and Lemma 3.1, it follows that

$$\begin{aligned} \left( P\left( G^{*},n-1\right) \right) ^{2}\ge P\left( G^{*},n\right) P\left( G^{*},n-2\right) . \end{aligned}$$
(24)

Thus, by (24) and Theorem 3.3, the theorem holds. □

By Theorem 3.4, we have the following

Corollary 3.4

Suppose that G is a 2-connected (n, m)-graph and w is any vertex in G with \(d(w)=n-1\). If \(m\le (\frac{\sqrt{2}}{2}+2)n-4.5-\sqrt{2}\), then

$$\begin{aligned} \mu (G)\ge \mu \left( (G-w)\cup K_{1}\right) . \end{aligned}$$
(25)

Theorem 3.5

For any wheel graph \(W_{n}\ (n\ge 4)\) and any vertex x in \(W_{n}\), one has \(\mu (W_{n})\ge \mu ((W_{n}-x)\cup K_{1})\).

Proof

Let \(W_{n} \ (n\ge 4)\) be the wheel of order n and x be a vertex in \(W_{n}\). The vertex x may be divided into the following two cases.

Case 1.   \(d(x)=n-1\), namely, x lies in the center of \(W_{n}\).

It is clear that \(W_{n}\) is a connected \((n,2n-2)\) graph and x is not a cut vertex in \(W_{n}\). By Theorem 3.4, one may deduce that \(\mu (W_{n})\ge \mu ((W_{n}-x)\cup K_{1})\) for \(n\ge 6\). And it is easy to verify that the inequality also holds for \(n=4,5\).

Case 2.   \(d(x)=3\), namely, x lies in the rim of \(W_{n}\).

Let \(H=(W_{n}-x)\cup K_{1}\). Since \(d(x)=3\), it follows that

$$\begin{aligned} P(H,\lambda )=\lambda P\left( W_{n}-x,\lambda \right) =\lambda ^{2}(\lambda -1)(\lambda -2)^{n-3}. \end{aligned}$$
(26)

And it is clear that

$$\begin{aligned} P\left( W_{n},\lambda \right) =\lambda P\left( C_{n-1},\lambda -1\right) =\lambda \left[ (\lambda -2)^{n-1}+(-1)^{n-1}(\lambda -2)\right] . \end{aligned}$$
(27)

Thus, by (4), (26) and (27), we have

$$\begin{aligned} \tau \left( W_{n},H,\lambda \right)&=P\left( W_{n},\lambda \right) P(H,\lambda -1)-P\left( W_{n},\lambda -1\right) P(H,\lambda )\nonumber \\&=\lambda (\lambda -2)(\lambda -1)^{2}\left\{ (\lambda -3)^{n-3}\left[ (\lambda -2)^{n-1}+(-1)^{n-1}(\lambda -2)\right] \right. \nonumber \\&\left. \quad -\lambda (\lambda -2)^{n-4}\left[ (\lambda -3)^{n-1}+(-1)^{n-1}(\lambda -3)\right] \right\} . \end{aligned}$$
(28)

According to the parity of n, we can divide into the following two subcases.

Case 2.1.    n is even.

For \(\lambda \ge 4\), by (28), we obtain

$$\begin{aligned} \tau \left( W_{n},H,\lambda \right)&=\lambda (\lambda -2)(\lambda -1)^{2}\left\{ (\lambda -3)^{n-3}\left[ (\lambda -2)^{n-1}-(\lambda -2)\right] \right. \nonumber \\&\left. \quad -\lambda (\lambda -2)^{n-4}\left[ (\lambda -3)^{n-1}-(\lambda -3)\right] \right\} \nonumber \\&=\lambda (\lambda -2)(\lambda -1)^{2}\left\{ (\lambda -2)^{n-4}(\lambda -3)^{n-3}\left[ (\lambda -2)^{3}-\lambda (\lambda -3)^{2}\right] \right. \nonumber \\&\left. \quad +\lambda (\lambda -3)(\lambda -2)^{n-4}-(\lambda -2)(\lambda -3)^{n-3}\right\} \nonumber \\&=\lambda (\lambda -2)(\lambda -1)^{2}\left\{ (3\lambda -8)(\lambda -2)^{n-4}(\lambda -3)^{n-3}\right. \nonumber \\&\left. \quad +\lambda (\lambda -3)(\lambda -2)^{n-4}-(\lambda -2)(\lambda -3)^{n-3}\right\} \nonumber \\&\ge \lambda (\lambda -2)(\lambda -1)^{2}\left\{ (3\lambda -8)(\lambda -2)^{n-4}(\lambda -3)^{n-3}\right\} \nonumber \\&> 0. \end{aligned}$$
(29)

Case 2.2.   n is odd.

For \(\lambda \ge 4\), by (28), we have

$$\begin{aligned} \tau \left( W_{n},H,\lambda \right)&=\lambda (\lambda -2)(\lambda -1)^{2}\left\{ (\lambda -3)^{n-3}\left[ (\lambda -2)^{n-1}+(\lambda -2)\right] \right. \nonumber \\&\left. \quad -\lambda (\lambda -2)^{n-4}\left[ (\lambda -3)^{n-1}+(\lambda -3)\right] \right\} \nonumber \\&=\lambda (\lambda -2)(\lambda -1)^{2}\left\{ (\lambda -2)^{n-4}(\lambda -3)^{n-3}\left[ (\lambda -2)^{3}-\lambda (\lambda -3)^{2}\right] \right. \nonumber \\&\left. \quad +(\lambda -2)(\lambda -3)^{n-3}-\lambda (\lambda -3)(\lambda -2)^{n-4}\right\} \nonumber \\&=\lambda (\lambda -2)(\lambda -1)^{2}\left\{ (3\lambda -8)(\lambda -2)^{n-4}(\lambda -3)^{n-3}\right. \nonumber \\&\left. \quad +(\lambda -2)(\lambda -3)^{n-3}-\lambda (\lambda -3)(\lambda -2)^{n-4}\right\} \nonumber \\&\ge \lambda (\lambda -2)(\lambda -1)^{2}\left\{ (\lambda -2)(\lambda -3)^{n-3}\right\} \nonumber \\&> 0. \end{aligned}$$
(30)

Combining (29) with (30), we have

$$\begin{aligned} \tau \left( W_{n},H,\lambda \right) >0 \end{aligned}$$

for \(\lambda \ge 4\). Hence \(\tau (W_{n},H,n)> 0 \ (n\ge 4)\). By Lemma 2.1, we have

$$\begin{aligned} \mu (W_{n})>\mu (H)=\mu \left( (W_{n}-x)\cup K_{1}\right) . \end{aligned}$$

Thus, the theorem holds.       □

Remark 3

Let G be a chordal graph or 2-tree and H be a subgraph of G. By the results in [4, 5], \(\mu (G)\ge \mu (H)\). It is clear that Conjecture 1 holds for a chordal graph or 2-tree G. In addition, for a vertex w in G with \(d(w)\ge 1\), if H is a subgraph obtained from G by deleting all the edges which are incident to w, then \(H\cong (G-w)\cup K_{1}\). Therefore \(\mu (G)\ge \mu (H)=\mu ((G-w)\cup K_{1})\). It means that Conjecture 2 also holds for a chordal graph or 2-tree G.