





















Let $χ(G)$ denote the chromatic number of a graph and $χ_v(G)$ denote the vector chromatic number. For all graphs $χ_v(G) \le χ(G)$ and for some graphs $χ_v(G) \ll χ(G)$. Galtman proved that Hoffman's well-known lower bound for $χ(G)$ is in fact a lower bound for $χ_v(G)$. We prove that two more spectral lower bounds for $χ(G)$ are also lower bounds for $χ_v(G)$. We then use one of these bounds to derive a new characterization of $χ_v(G)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。