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 that \[ 1 + \max\left(\frac{n^+}{n^-} , \frac{n^-}{n^+}\right) \le \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.
@article{10_37236_6404,
author = {Clive Elphick and Pawel Wocjan},
title = {An inertial lower bound for the chromatic number of a graph},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {1},
doi = {10.37236/6404},
zbl = {1358.05104},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6404/}
}
TY - JOUR
AU - Clive Elphick
AU - Pawel Wocjan
TI - An inertial lower bound for the chromatic number of a graph
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/6404/
DO - 10.37236/6404
ID - 10_37236_6404
ER -
%0 Journal Article
%A Clive Elphick
%A Pawel Wocjan
%T An inertial lower bound for the chromatic number of a graph
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/6404/
%R 10.37236/6404
%F 10_37236_6404
Clive Elphick; Pawel Wocjan. An inertial lower bound for the chromatic number of a graph. The electronic journal of combinatorics, Tome 24 (2017) no. 1. doi: 10.37236/6404
