An inertial lower bound for the chromatic number of a graph

Abstract

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 χ(G) \mbox{ and conjecture that } 1 + \max\left(\frac{n^+}{n^-} , \frac{n^-}{n^+}\right) \le χ_f(G) \] We investigate extremal graphs for these bounds and demonstrate that this inertial bound is not a lower bound for the vector chromatic number. We conclude with a discussion of asymmetry between $n^{+}$ and $n^{-}$, including some Nordhaus-Gaddum bounds for inertia.