Box complexes, neighborhood complexes, and the chromatic number (Q1881691): Difference between revisions

The connectivity of certain simplicial complexes (neighborhood complex, box complexes) associated with a graph yields lower bounds for the chromatic number. Since L. Lovász' proof of the Kneser conjecture [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)] this insight has been explored in a number of directions; for a recent survey see \textit{J. Matoušek} and the reviewer [Topological lower bounds for the chromatic number: a hierarchy, Jahresber. Dtsch. Math.-Ver. 106, 71--90 (2004; Zbl 1063.05047)]. It is known that the topological lower bounds for the chromatic number are weak for graphs with few complete bipartite subgraphs. In particular, for \(C_4\)-free graphs the lower bound will be trivial. This is extended in this paper to graphs without a \(K_{\ell,m}\) subgraphs: For these the index of the box complex is at most \(\ell+m-3\), so the lower bound for the chromatic number is no better than \(\ell+m-1\). This is derived as part of a detailed study of some box complexes.