An inertial lower bound for the chromatic number of a graph (Q521386)

Summary: 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\bigg(\frac{n^+}{n^-},\frac{n^-}{n^+}\bigg) \leq \chi(G) \] and conjecture that \[ 1 + \max\bigg(\frac{n^+}{n^-},\frac{n^-}{n^+}\bigg) \leq \chi_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.