Generalised Mycielski graphs and bounds on chromatic numbers

Abstract

We prove that the coindex of the box complex $\mathrm{B}(H)$ of a graph $H$ can be measured by the generalised Mycielski graphs which admit a homomorphism to it. As a consequence, we exhibit for every graph $H$ a system of linear equations solvable in polynomial time, with the following properties: If the system has no solutions, then $\mathrm{coind}(\mathrm{B}(H))+2\le 3$; if the system has solutions, then $\chi (H)\ge 4$. We generalise the method to other bounds on chromatic numbers using linear algebra.