An Inertial Lower Bound for the Chromatic Number of a Graph

[摘要] Let $\chi(G$) and $\chi_f(G)$ denote the chromatic and fractional chromatic numbers of a graph $G$, and let $(n^+ , n^0 , n^-)$ denote the inertia of $G$. We prove that:\[1 + \max\left(\frac{n^+}{n^-} , \frac{n^-}{n^+}\right) \le \chi(G)\] and conjecture

[学科分类] 离散数学和组合数学

[关键词] Spectral graph theory;Chromatic number;Fractional chromatic number