An inertial lower bound for the chromatic number of a graph

Clive Elphick, Pawel Wocjan

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…