November 11, 2025
Let \(G\) be a simple graph on \(n\) vertices and \(m\) edges with chromatic number \(\chi\), and let \(\lambda_n\) denote the least adjacency eigenvalue. Solving a conjecture of Fan, Yu and Wang [Electron. J. Combin., 2012], we prove that when \(3\le \chi\le n-1\), the chromatic number satisfies the following upper bound: \[\chi \le \left(\frac{n}{2}+1+\lambda_n\right) + \sqrt{\left(\frac{n}{2}+1+\lambda_n\right)^{2}-4(\lambda_n+1)\left(\lambda_n+\frac{n}{2}\right)},\] with equality if and only if \(G \cong \left(K_{\frac{\chi}{2}}\cup\tfrac{n-\chi}{2}K_1\right) \vee \left(K_{\frac{\chi}{2}}\cup\tfrac{n-\chi}{2}K_1\right)\), where both \(n\) and \(\chi\) are even. This extends the validity of Fan–Yu–Wang’s bound from the range \(3\le \chi\le \frac{n}{2}\) to the full range \(3\le \chi\le n-1\).
We also compare this bound with the well-known bound due to Wilf that \(\chi \le 1 + \lambda_1\), where \(\lambda_1\) denotes the largest eigenvalue. In particular we show that while Wilf’s bound is an upper bound for some parameters larger than \(\chi\), this bound using \(\lambda_n\) is not an upper bound for these parameters. We conclude with a similar conjectured upper bound for \(\chi(G)\), which uses \(m\) in place of \(n\).
Let \(G=(V,E)\) be a simple graph of order \(n\) with vertex set \(V=V(G)\) and edge set \(E=E(G)\). The adjacency matrix of \(G\) is the \(n\times n\) \(0\)–\(1\) matrix \(A(G)=[a_{ij}]\), where \(a_{ij}=1\) if \(v_i\) is adjacent to \(v_j\) and \(a_{ij}=0\) otherwise. The eigenvalues of \(A(G)\) are called the eigenvalues of the graph \(G\). Since \(A(G)\) is symmetric, all eigenvalues are real; we list them as \[\lambda_1(G)\ge \lambda_2(G)\ge \cdots \ge \lambda_n(G).\]
The chromatic number of a graph \(G\), denoted by \(\chi(G)\), is the least number of colors needed to color \(V(G)\) so that adjacent vertices receive distinct colors. There has been extensive research on the connection between eigenvalues and the chromatic number of a graph. Wilf [1] proved that \(\chi(G)\le 1+\lambda_1(G)\). For connected graphs, equality holds if and only if \(G\) is a complete graph or an odd cycle. Hoffman [2] showed that \(\chi(G)\ge 1-\frac{\lambda_1(G)}{\lambda_n(G)}\). Elphick, Tang and Zhang [3] proved lower bounds on chromatic numbers in terms of \(p\)-energies, which substantially generalize the Hoffman bound.
We use the following notation. Let \(K_n\) (resp. \(O_n\)) denote the complete (resp. empty) graph on \(n\) vertices; note that \(O_n = nK_1\), the disjoint union of \(n\) isolated vertices. For two vertex-disjoint graphs \(H_1=(V_1,E_1)\) and \(H_2=(V_2,E_2)\), their disjoint union is \[H_1\cup H_2\quad\text{with}\quad V(H_1\cup H_2)=V_1\cup V_2,\;\;E(H_1\cup H_2)=E_1\cup E_2,\] and their join is \[H_1\vee H_2\quad\text{with}\quad V(H_1\vee H_2)=V_1\cup V_2,\;\; E(H_1\vee H_2)=E_1\cup E_2\cup\{uv:\;u\in V_1,\;v\in V_2\}.\] (Equivalently, every vertex of \(H_1\) is made adjacent to every vertex of \(H_2\).) We also write \(K_{a,b}\) for the complete bipartite graph with parts of sizes \(a\) and \(b\); note that \(K_{a,b}=O_a\vee O_b\).
It is immediate that \(\chi(G)=n\) if and only if \(G=K_n\); \(\chi(G)=1\) if and only if \(G=O_n\). Moreover, \(\chi(G)=2\) precisely when \(G\) is bipartite. A result of Constantine [4] (see also [5]) shows that among all \(n\)-vertex graphs (or all \(n\)-vertex bipartite graphs), the unique graph minimizing the least eigenvalue is the complete bipartite graph \(K_{\lceil n/2\rceil,\lfloor n/2\rfloor}=O_{\lceil n/2\rceil}\vee O_{\lfloor n/2\rfloor}\). Accordingly, the present work focuses on graphs with \(\chi(G) \ge 3\).
In [5], Fan, Yu and Wang established an upper bound for the chromatic number of a graph in terms of its order and least adjacency eigenvalue, which also appears in Stanić’s book [6].
Theorem 1 ([5]). Let \(G\) be a graph of order \(n\) with chromatic number \(3\leq \chi \leq \frac{n}{2}\) and least adjacency eigenvalue \(\lambda_n\). Then \[\chi \le \left(\frac{n}{2}+1+\lambda_n\right) + \sqrt{\left(\frac{n}{2}+1+\lambda_n\right)^2 - 4(\lambda_n+1)\left(\lambda_n + \frac{n}{2}\right)},\] with equality if and only if \(G \cong \left(K_{\frac{\chi}{2}}\cup\tfrac{n-\chi}{2}K_1\right) \vee \left(K_{\frac{\chi}{2}}\cup\tfrac{n-\chi}{2}K_1\right)\), where both \(n\) and \(\chi\) are even.
Fan, Yu and Wang [5] conjectured that the above bound continues to hold for \(\frac{n}{2}<\chi\le n-1\). In this paper we resolve this conjecture.
Let us briefly explain the new difficulty in the range \(\chi>n/2\). After reducing the problem to the two-parameter family \(G(a,a_0)\), the proof in [5] treats \(a\) and \(a_0\) as real variables and compares \(f(a,a_0,\lambda)\) with \(f\left(\frac{\chi}{2},\frac{n-\chi}{2},\lambda\right)\) for fixed \(\lambda\in(-n/2,-1)\). This comparison is obtained from sign estimates for partial derivatives, and these estimates use inequalities that follow from \(\chi\le n/2\). For example, the positivity of \(n-\chi+1+\lambda\) follows in that range from \(\lambda>-n/2\) and \(\chi\le n/2\). When \(\chi>n/2\), such sign information is no longer uniform over the feasible region, so the same calculus argument does not seem to yield the desired minimization directly.
Our main observation is that the root comparison can instead be made at a single point. Lemma 3 shows that every relevant quartic has exactly one negative real root. Hence, if \(\xi\) denotes the negative root of the balanced polynomial \(f\left(\frac{\chi}{2},\frac{n-\chi}{2},\lambda\right)\), then it is enough to prove \(f(a,a_0,\xi)\ge 0\) for every feasible pair \((a,a_0)\). After centering the parameters at the balanced point, the difference \(f(a,a_0,\lambda)-f\left(\frac{\chi}{2},\frac{n-\chi}{2},\lambda\right)\) has an explicit form. Substituting the quadratic equation satisfied by \(\xi\) reduces the desired nonnegativity to a short completion-of-squares argument.
We follow the notation in [5]. Given positive integers \(n\) and \(\chi\) with \(3\le \chi\le n-1\), we introduce a family of graphs defined by \[G(a,a_0) := \left(K_a\cup O_{a_0}\right) \vee \left(K_b\cup O_{b_0}\right),\] where \[\label{eq:feasible1} 1\le a\le \chi-1,\qquad b=\chi-a,\qquad a_0,b_0\ge0,\qquad a_0+b_0=n-\chi.\tag{1}\] We call a pair \((a,a_0)\) feasible if the integers \(a\) and \(a_0\) satisfy 1 . It is immediate that \(\chi(G(a,a_0))=\chi\), and since \(G(a,a_0)\) is connected but not complete, we have \(\lambda_n(G(a,a_0))<-1\).
By [5], the least eigenvalue \(\lambda_n(G(a,a_0))\) is the smallest real root of the quartic polynomial: \[\label{eq:quartic} f(a,a_0,\lambda) := \lambda^2(\lambda-a+1)(\lambda-b+1) -\bigl[(b+b_0)\lambda-b_0(b-1)\bigr] \bigl[(a+a_0)\lambda-a_0(a-1)\bigr],\tag{2}\] where \(b=\chi-a\) and \(b_0=n-\chi-a_0\), and throughout the paper \(n\) and \(\chi\) are regarded as fixed numbers.
We recall the following structural lemma from [5].
Lemma 2 ([5]). Among all graphs of order \(n\) and chromatic number \(\chi\), where \(3\le \chi\le n-1\), if a graph \(G\) is one whose least eigenvalue attains the minimum, then \(G\) must be of the form \(G(a,a_0)\) for some \(a\) and \(a_0\).
We also need the following lemma concerning the number of negative roots of the polynomial \(f(a,a_0,\lambda)\) defined in 2 .
Lemma 3. For every feasible pair \((a,a_0)\), the polynomial \(f(a,a_0,\lambda)\) has exactly one negative real root (counted with multiplicity). Moreover, \(f(a,a_0,0)\le 0\) and \(\lim_{\lambda\to-\infty} f(a,a_0,\lambda)=+\infty\).
Proof. Write \(g(x):=f(a,a_0,-x)\). Let \(b=\chi-a\) and \(b_0=n-\chi-a_0\). A direct expansion gives \[\begin{align} g(x) &=x^2(x+ a - 1)(x+ b - 1)-((b + b_0)x+ b_0(b - 1))((a + a_0)x+ a_0(a - 1))\\ &=x^4+(a+b-2) x^3+\left((a-1)(b-1)-(a+a_0)(b+b_0)\right)x^2\\ &\qquad-\left((b+b_0)a_0(a-1)+(a+a_0)b_0(b-1)\right)x-a_0(a-1)b_0(b-1). \end{align}\] Hence the coefficient signs of \(g\) are \[+\;,\quad \ge 0\;,\quad -\;,\quad \le 0\;,\quad \le 0.\]Ignoring possible zeros, the sign sequence has exactly one sign change (from \(+\) to \(-\)). By Descartes’ rule of signs [7], \(g\) has exactly one positive real root with multiplicity \(1\). Therefore \(f(a,a_0,\lambda)\) has exactly one real root (counted with multiplicity) in \((-\infty,0)\).
Finally, \(f(a,a_0,0)=-b_0(b-1)\,a_0(a-1)\le 0\), and since the leading coefficient of \(f\) is \(+1\), we have \(\lim_{\lambda\to-\infty}f(a,a_0,\lambda)=+\infty\). ◻
In this section we extend [5] to the full range \(3\le \chi\le n-1\).
Theorem 4. Let \(G\) be a simple graph of order \(n\) with chromatic number \(\chi\) satisfying \(3\le \chi\le n-1\). Then the least adjacency eigenvalue \(\lambda_n\) satisfies \[\lambda_n \ge -\frac{n-\chi+2+\sqrt{(n-\chi-2)^2+4\chi(n-\chi)}}{4},\] with equality if and only if \(G \cong \left(K_{\frac{\chi}{2}}\cup\tfrac{n-\chi}{2}K_1\right) \vee \left(K_{\frac{\chi}{2}}\cup\tfrac{n-\chi}{2}K_1\right)\), where both \(n\) and \(\chi\) are even.
Proof. By Lemma 2, to determine the extremal value of \(\lambda_n(G)\) among all graphs of order \(n\) and chromatic number \(\chi\), it suffices to minimize the smallest real root of \(f(a,a_0,\lambda)\) over all feasible pairs \((a,a_0)\). Our goal is to prove that, for every feasible pair \((a,a_0)\), \[\label{eq:least95text1} \text{the smallest real root of }f\left(\tfrac{\chi}{2},\tfrac{n-\chi}{2},\lambda\right) \;\text{is not greater than that of } f(a,a_0,\lambda).\tag{3}\] Let \(\xi\) denote the smallest real root of \(f\left(\tfrac{\chi}{2},\tfrac{n-\chi}{2},\lambda\right)\). In view of Lemma 3, each \(f(a,a_0,\lambda)\) has exactly one real root on \((-\infty,0)\); hence Eq. 3 is equivalent to showing that \[\label{eq:least95text2} f(a,a_0,\xi)\;\ge\;0\qquad\text{for every feasible pair }(a,a_0).\tag{4}\] Indeed, if \(f(a,a_0,\xi)\ge 0\), then \(\xi\) lies to the left of (or coincides with) the unique negative root of \(f(a,a_0,\lambda)\), so the smallest real root of \(f(a,a_0,\lambda)\) is at least \(\xi\).
Fix \(n,\chi\) and write \[\label{eq:compute95LR951} p:=\frac{n-\chi}{2}>0,\quad q:=\frac{\chi}{2}-1>0,\quad M:=\frac{n}{2}\lambda,\tag{5}\] \[\label{eq:compute95LR952} a=\frac{\chi}{2}+t,\quad b=\frac{\chi}{2}-t,\quad a_0=p+s,\quad b_0=p-s,\tag{6}\] so that \(|t|\le q\) and \(|s|\le p\). Define \[\Delta(s,t;\lambda):=f(a,a_0,\lambda)-f\left(\tfrac{\chi}{2},\tfrac{n-\chi}{2},\lambda\right).\] The next claim is a purely algebraic identity.
Claim 1. For all \(\lambda\in\mathbb{R}\), \[\Delta(s,t;\lambda)=p(p-2\lambda) t^2+(\lambda-q)^2 s^2-s^2t^2+2\lambda(\lambda+1) st.\]
Proof of Claim 1. Write \[L:=(b+b_0)\lambda-b_0(b-1),\qquad R:=(a+a_0)\lambda-a_0(a-1),\] a direct calculation with 5 and 6 gives \[L=(M-pq)-st-\left(s(\lambda-q)+t(\lambda-p)\right),\quad R=(M-pq)-st+\left(s(\lambda-q)+t(\lambda-p)\right),\] hence \[LR=(M-pq)^2-2(M-pq)st-\left[(\lambda-q)^2s^2+(\lambda-p)^2t^2+2(\lambda-q)(\lambda-p)st\right]+s^2t^2.\]Using \[(\lambda-a+1)(\lambda-b+1)=(\lambda-q-t)(\lambda-q+t)=(\lambda-q)^2-t^2,\]we know that\[f(a,a_0,\lambda)=\lambda^2 \left[(\lambda-q)^2-t^2\right]-LR, \quad f\left(\tfrac{\chi}{2},\tfrac{n-\chi}{2},\lambda\right)=\lambda^2 (\lambda-q)^2 -(M-pq)^2,\] it follows that \(\Delta(s,t;\lambda) = -\lambda^2 t^2 -LR + (M-pq)^2\). Now\[\begin{align} \Delta(s,t;\lambda)&= -\lambda^2 t^2 +2(M-pq)st +\left[(\lambda-q)^2s^2+(\lambda-p)^2t^2+2(\lambda-q)(\lambda-p)st\right]-s^2t^2 \\&=\left( (\lambda-p)^2-\lambda^2 \right)t^2 + (\lambda-q)^2s^2+2st \left[(M-pq)+(\lambda-p)(\lambda-q) \right] - s^2t^2. \end{align}\]Recall that \((\lambda-p)^2-\lambda^2=p(p-2\lambda)\) and \[(M-pq)+(\lambda-p)(\lambda-q)=\lambda^2-(p+q-\tfrac{n}{2})\lambda=\lambda(\lambda+1),\]we obtain \[\Delta(s,t;\lambda)=p(p-2\lambda) t^2+(\lambda-q)^2 s^2-s^2t^2+2\lambda(\lambda+1) st,\]as desired. ◻
Recall that \(\xi\) is the smallest real root of the polynomial \[f\left(\tfrac{\chi}{2},\tfrac{n-\chi}{2},\lambda\right)=\lambda^2(\lambda-q)^2-(M-pq)^2.\] By Lemma 3, for each feasible pair \((a,a_0)\), \(f(a,a_0,\lambda)\) has exactly one real root on \((-\infty,0)\), and therefore \(\xi<0\) is the unique negative root of \(f\left(\tfrac{\chi}{2},\tfrac{n-\chi}{2},\lambda\right)\) characterized by \[\label{eq:xi-eqn} \lambda(\lambda-q)=-(M-pq)\quad\Longleftrightarrow\quad \lambda^2+(1+p)\lambda-pq=0.\tag{7}\] From 7 we will use the convenient identity \[\label{eq:key-identity} \xi(\xi+1)=p (q-\xi).\tag{8}\] To prove Eq. 4 , it suffices to prove \[\label{eq:least95text3} \Delta(s,t;\xi) \ge 0\qquad\text{for every feasible pair }(a,a_0).\tag{9}\] Define \[\mu:=-\xi>0,\qquad \alpha:=p+2\mu=p-2\xi>0,\qquad \beta:=q+\mu=q-\xi>0.\]By Claim 1 and 8 , we can rewrite \[\Delta(s,t;\xi) =(\beta^2-t^2)s^2+2p\beta t s+p\alpha t^2.\] For each fixed \(t\), this is a convex quadratic polynomial in \(s\) with leading coefficient \(\beta^2-t^2>0\) (since \(\beta>q\ge |t|\)). Completing the square gives \[\label{eq:Delta-min} \Delta(s,t;\xi) =(\beta^2-t^2)\left(s+\frac{p\beta t}{\beta^2-t^2}\right)^2 +\frac{pt^2}{\beta^2-t^2}\left[\alpha(\beta^2-t^2)-p\beta^2\right].\tag{10}\] Hence \[\label{eq:min-s95p1} \min_{|s|\leq p}\Delta(s,t;\xi)\geq\min_{s\in\mathbb{R}}\Delta(s,t;\xi) =\frac{pt^2}{\beta^2-t^2}\left[\alpha(\beta^2-t^2)-p\beta^2\right].\tag{11}\] Thus, to prove Eq. 9 , it suffices to prove \[\label{eq:least95text4} \alpha(\beta^2-t^2)\geq p\beta^2 \qquad\text{for any }|t|\le q.\tag{12}\] In particular, it is enough to verify that \(\alpha(\beta^2-q^2)-p\beta^2 \geq 0\). Using \(\mu^2=(1+p)\mu+pq\) from 7 , we obtain \[\begin{align} \alpha(\beta^2-q^2)-p\beta^2 &=(p+2\mu)\mu(2q+\mu)-p(q+\mu)^2=2\mu^3+4\mu^2 q-pq^2 \\ &=2\mu^3+ 4q((1 + p)\mu + pq)-pq^2\\ &=2\mu^3+4(1+p)\mu q+3pq^2\;>\;0. \end{align}\] Therefore \(\min_{|s|\leq p}\Delta(s,t;\xi)\ge 0\) for all \(|t|\le q\), this completes the proof of Eq. 3 . The least root of the quadratic equation 8 is\[\xi=-\frac{n-\chi+2+\sqrt{(n-\chi-2)^2+4\chi(n-\chi)}}{4}.\]By Eq. 3 , it follows that for every feasible pair \((a,a_0)\), the smallest real root of \(f(a,a_0,\lambda)\) is greater than or equal to \(\xi\). Hence, by Lemma 2, for all graphs of order \(n\) with chromatic number \(\chi\) satisfying \(3\le \chi\le n-1\), the least adjacency eigenvalue \(\lambda_n\) satisfies \[\label{eq:least95text100} \lambda_n \ge \xi= -\frac{n-\chi+2+\sqrt{(n-\chi-2)^2+4\chi(n-\chi)}}{4}.\tag{13}\]
Now we consider the equality condition. If \(\lambda_n(G) = \xi\), then \(G\) must be of the form \(G(a,a_0)\) for some feasible integers \(a\) and \(a_0\) by Lemma 2. Hence the smallest real root of \(f\!\left(\tfrac{\chi}{2},\tfrac{n-\chi}{2},\lambda\right)\) coincides with that of \(f(a,a_0,\lambda)\), which forces \(\Delta(s,t;\xi)=0\). Since \(\alpha(\beta^2-q^2)-p\beta^2>0\), by 11 the only way for \(\Delta(s,t;\xi)=0\) is to have \(t=0\). Substituting \(t=0\) into \(\Delta(s,t;\xi)\) gives \[\Delta(s,0;\xi)=(\beta^2-0)s^2=\beta^2 s^2.\] Thus \(\Delta(s,t;\xi)=0\) implies \(s=0\) as well, i.e.\((s,t)=(0,0)\). Equivalently, \(a=\tfrac{\chi}{2}\) and \(a_0=\tfrac{n-\chi}{2}\). This shows that the equality graph in 13 is precisely \[G\left(\tfrac{\chi}{2},\tfrac{n-\chi}{2}\right) =\left(K_{\frac{\chi}{2}}\cup\tfrac{n-\chi}{2}K_1\right) \vee \left(K_{\frac{\chi}{2}}\cup\tfrac{n-\chi}{2}K_1\right),\] where both \(n\) and \(\chi\) are even. ◻
By the same argument as in the proof of [5], we derive the following upper bound on the chromatic number in terms of its order and least adjacency eigenvalue.
Theorem 5. Let \(G\) be a graph of order \(n\) with chromatic number \(3\leq \chi \leq n-1\) and least adjacency eigenvalue \(\lambda_n\). Then \[\label{eq:chi-upper} \chi \le \left(\frac{n}{2}+1+\lambda_n\right) + \sqrt{\left(\frac{n}{2}+1+\lambda_n\right)^2 - 4(\lambda_n+1)\left(\lambda_n + \frac{n}{2}\right)},\qquad{(1)}\] with equality if and only if \(G \cong \left(K_{\frac{\chi}{2}}\cup\tfrac{n-\chi}{2}K_1\right) \vee \left(K_{\frac{\chi}{2}}\cup\tfrac{n-\chi}{2}K_1\right)\), where both \(n\) and \(\chi\) are even.
As noted above, Wilf proved that \(\chi(G)\le 1+\lambda_1(G)\). In fact, as proved by Wu and Elphick [8], \[\chi(G) \le \chi_\ell(G) \le \operatorname{col}(G) \le 1+\lambda_1(G),\] where \(\chi_\ell(G)\) denotes the list chromatic number and \(\operatorname{col}(G)\) denotes the coloring number. However, in Theorem 5 one cannot replace \(\chi(G)\) by \(\chi_\ell(G)\) or by \(\operatorname{col}(G)\).
When \(\chi = 2\), Theorem 4 simplifies to \(\lambda_n \ge -n/2\), which was proved by Constantine [4] for all graphs. Theorem 5 is therefore true when \(\chi = 2\), and we can let \(G=K_{3,3}\) for which \(n=6\) and the least adjacency eigenvalue is \(\lambda_n(G)=-3\). Plugging \(\lambda_n=-3\) and \(n=6\) into the right-hand side of ?? gives \[\left(\frac{n}{2}+1+\lambda_n\right)+ \sqrt{\left(\frac{n}{2}+1+\lambda_n\right)^{2}-4(\lambda_n+1)\left(\lambda_n+\frac{n}{2}\right)} =2.\] But since \(\operatorname{col}(K_{3,3})\ge \chi_\ell(K_{3,3})=3\), if \(\chi\) in Theorem 5 were replaced by \(\chi_\ell\) or \(\operatorname{col}\), it would falsely assert that \(\chi_\ell(K_{3,3})\le \operatorname{col}(K_{3,3})\le 2\). Therefore the chromatic number in Theorem 5 cannot be replaced by the list chromatic number or the coloring number.
Fan, Yu and Wang [5] demonstrated that their bound and Wilf’s bound are incomparable. To exemplify this incomparability, for the connected graphs in the Wolfram Mathematica database of graphs with \(n = 16\) and \(\chi \ge 3\):
Wilf’s bound outperforms Fan–Yu–Wang’s bound for 333 graphs;
Fan–Yu–Wang’s bound outperforms Wilf’s bound for 23 graphs; and
the bounds are equal for 3 graphs.
Fan–Yu–Wang’s bound performs comparatively well, for example, on some circulant, complete multipartite, and cone graphs.
In addition to proving Theorem 1, Fan, Yu and Wang also proved the following result [5]:
Theorem 6 ([5]). Among all graphs of order \(n\) and with chromatic number \(\chi\), where \(3 \leq \chi \leq n/2\), the graph \(G(\lceil\chi/2\rceil, \lfloor(n - \chi)/2\rfloor)\) is the unique one whose least eigenvalue attains the minimum.
Fan, Yu and Wang [5] also conjectured that this theorem remains true for the full range \(3\le \chi \le n-1\). This conjecture follows directly from Theorem 4 when both \(n\) and \(\chi\) are even. For the remaining parity cases, our fully algebraic approach appears to be less straightforward than the calculus-based approach used in [5]. At the symmetric point \((a,a_0)=(\tfrac{\chi}{2},\tfrac{n-\chi}{2})\), the characteristic polynomial can be factorized as a difference of squares, and thus the least root \(\xi\) satisfies a quadratic equation. Substituting this relation into \(\Delta\) is straightforward, and the nonnegativity of \(\Delta\) can then be easily verified. However, for instance, when both \(\chi\) and \(n\) are odd, we have \((a,a_0)=(\tfrac{\chi+1}{2},\tfrac{n-\chi}{2})\). In this case, the symmetry is broken, and the least root \(\zeta\) instead satisfies a quartic equation: \[\lambda^2(\lambda-q)^2-\left(\frac{n}{2}\lambda-pq\right)^2+\tfrac14 p (p-2\lambda)=0.\] Consequently, proving \(\tilde{\Delta}(s,t;\zeta):=f(a,a_0,\zeta)-f\left(\tfrac{\chi+1}{2},\tfrac{n-\chi}{2},\zeta\right) \ge0\) must be carried out over the half-integer lattice \(t\in\tfrac12+\mathbb{Z}\), with separate treatment required for the endpoint cases \(t=\tfrac12,\tfrac32,\) and \(t=q\) (since we may assume without loss of generality that \(a\ge b\), i.e., \(t\ge0\)). Each of these endpoint cases involves repeated eliminations using the above quartic identity, which is substantially more complicated than the algebraic substitution based on a quadratic equation. We believe the conclusion still holds, although a concise and unified algebraic proof covering all parity cases remains elusive.
In this paper, we resolved a conjecture of Fan, Yu and Wang by proving that their upper bound on the chromatic number also holds in the range \(\frac{n}{2}<\chi\le n-1\). We also note that this is a natural high-chromatic regime. For example, it contains all complete multipartite graphs of order \(n\) with \(k\) nonempty parts, where \(\frac{n}{2}<k\le n-1\), since such a graph has chromatic number \(k\). More generally, let \(H\) be a graph on \(h\) vertices, and let \(K_r\vee H\) denote the join of \(K_r\) and \(H\). Then \(K_r\vee H\) has order \(r+h\) and \(\chi(K_r\vee H)=r+\chi(H)\), because the colors used on \(K_r\) cannot be reused on \(H\). Hence \(K_r\vee H\) lies in the range \(\chi>n/2\) whenever \(r+\chi(H)>\frac{r+h}{2}\). If \(H\) is not complete, then \(K_r\vee H\) is also non-complete and has chromatic number at most \(r+h-1\). Thus the extension from \(3\le \chi\le n/2\) to the full range \(3\le \chi\le n-1\) covers a broad and varied class of high-chromatic graphs, not only a small near-complete exceptional family.
The parameter \(n/2\) in Theorem 1 is closely related to the universal lower bound \(\lambda_n\ge -n/2\). A related estimate of Powers [9] gives \(\lambda_n^2\le m\); indeed, \[2m=\sum_{i=1}^n\lambda_i^2\ge \lambda_1^2+\lambda_n^2\ge 2\lambda_n^2.\] Wu and Elphick [8] proved that \[\chi(\chi - 1) \le (\lambda_1 + 1)\lambda_1 \le 2m.\] By analogy with Theorem 1, this suggests the following conjecture, in which \(m\) replaces \(n/2\), \(\chi(\chi - 1)\) replaces \(\chi\), and \(-\lambda_n^2\) replaces \(\lambda_n\). Note that this conjectured bound is at most \(2m\).
Conjecture 7. For any non-empty graph \(G\),\[\chi(\chi - 1) \le (m + 1 - \lambda_n^2) + \sqrt{(m + 1 - \lambda_n^2)^2 - 4(\lambda_n^2 - 1)(\lambda_n^2 - m)}.\]
Conjecture 7 is exact for \(K_n\) and complete bipartite graphs, and the proof is trivial for bipartite graphs. We have verified Conjecture 7 for graphs of order at most 9, and graphs with order at most \(100\) in the Wolfram Mathematica database. As for Theorem 5, the chromatic number in Conjecture 7 cannot be replaced by the list chromatic number or the coloring number.
This edge-based conjecture typically performs better than the vertex-based bound proved in this paper. For example for the connected graphs in the Mathematica database with 16 vertices:
Conjecture 7 outperforms Fan–Yu–Wang’s bound ?? for 384 graphs;
Fan–Yu–Wang’s bound ?? outperforms Conjecture 7 for 34 graphs; and
the bounds are equal for 2 graphs.
The authors thank Jie Ma for helpful comments and suggestions, and Hitesh Kumar for pointing out several typos in an earlier version of this paper. They are also grateful to the anonymous referees for their careful reading and valuable comments.