





















Let $G$ be a simple graph on $n$ vertices and $m$ edges with chromatic number $χ$, and let $λ_n$ denote the least adjacency eigenvalue. Solving a conjecture of Fan, Yu and Wang~[Electron. J. Combin., 2012], we prove that when $3\le χ\le n-1$, the chromatic number satisfies the following upper bound: $$ χ\le \left(\frac{n}{2}+1+λ_n\right) + \sqrt{\left(\frac{n}{2}+1+λ_n\right)^{2}-4(λ_n+1)\left(λ_n+\frac{n}{2}\right)}, $$ with equality if and only if $G \cong \left(K_{\fracχ{2}}\cup\tfrac{n-χ}{2}K_1\right) \vee \left(K_{\fracχ{2}}\cup\tfrac{n-χ}{2}K_1\right)$, where both $n$ and $χ$ are even. This extends the validity of Fan--Yu--Wang's bound from the range $3\le χ\le \frac{n}{2}$ to the full range $3\le χ\le n-1$. We also compare this bound with the well-known bound due to Wilf that $χ\le 1 + λ_1$, where $λ_1$ denotes the largest eigenvalue. In particular we show that while Wilf's bound is an upper bound for some parameters larger than $χ$, this bound using $λ_n$ is not an upper bound for these parameters. We conclude with a similar conjectured upper bound for $χ(G)$, which uses $m$ in place of $n$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。