On Bj\"{o}rner and Lov\'{a}sz's conjecture

In the way of proving Kneser’s conjecture, L'{a}szl'{o} Lov'{a}sz settled out a new lower bound for the chromatic number of graphs. He showed that if the hom complex $\mathrm{\mid }\mathrm{\mid }Hom({\mathcal{K}}_2,H)\mathrm{\mid }\mathrm{\mid }$ of a graph $H$ is topologically $k$-connected, then its chromatic number, $\chi (H)$, is at least $k+3$. After that, he made the following conjecture, to provide a better lower bound on the chromatic number of graphs. If $\mathrm{\mid }\mathrm{\mid }Hom(C_{2r+1},H)\mathrm{\mid }\mathrm{\mid }$ is $k$-connected, then $\chi (H)\ge k+4$, where $C_{2r+1}$ is an odd cycle of length $2r+1$. Finally, Bj"{o}rner and Lov'{a}sz proposed a generalization of the Lov'{a}sz conjecture as follows. If $\mathrm{\mid }\mathrm{\mid }Hom(T,H)\mathrm{\mid }\mathrm{\mid }$ is $k$-connected, then $\chi (H)\geq k+\chi (T) +1$. The first conjecture was originally confirmed by Babson and Kozlov, by complicated computations with spectral sequences. But the second one was disproved by Hoory and Linial. So, after that, a graph $T$ is called a test graph if for every graph $H$, the $k$-connectedness of $\mathrm{\mid }\mathrm{\mid }Hom(T,H)\mathrm{\mid }\mathrm{\mid }$ implies $\chi (H)\ge k+1+\chi (H)$. In this paper, we prove that if a graph $F$ possess an involutive automorphism that flips some edge; then it is a test graph. As a corollary, we give a purely combinatorial proof of the Lov'{a}sz conjecture; odd cycles are test graphs. Indeed, although the Bj"{o}rner and Lov'{a}sz conjecture is not true in general, we show that a slight modification of the conjecture is always true. More precisely, we show that for any graph $T$, there is a supergraph $T\subseteq \widehat{T}$ with $\chi (\widehat{T})\le \chi (T)+1$, such that $\widehat{T}$ is a test graph.