An inertial lower bound for the chromatic number of a graph

الأصل · EN

Let χ(G) and χf(G) denote the chromatic and fractional chromatic numbers of a graph G, and let (n+, n⁰, n-) denote the inertia of G. We prove that: 1 + (n+/n-, n-/n+) ≤ χ(G) and conjecture that 1 + (n+/n-, n-/n+) ≤ χ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.