On Björner and Lovász's conjecture

Abstract

In the way of proving Kneser's conjecture, László Lovász settled out a new lower bound for the chromatic number of graphs. He showed that if the hom complex $||Hom({\mathcal{K}}_2,H)||$ 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 $||Hom(C_{2r+1},H)||$ is $k$-connected, then $\chi (H)\ge k+4$, where $C_{2r+1}$ is an odd cycle of length $2r+1$. Finally, Björner and Lovász proposed a generalization of the Lovász conjecture as follows. If $||Hom(T,H)||$ is $k$-connected, then $\chi (H)\ge 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 $||Hom(T,H)||$ 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ász conjecture; odd cycles are test graphs. Indeed, although the Björner and Lová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 \hat{T}$ with $\chi (\hat{T})\le \chi (T)+1$, such that $\hat{T}$ is a test graph.

arXiv commentThere is an error in one of my results