Chromatic number, Clique number, and Lovász's bound: In a comparison

Abstract

In the way of proving Kneser's conjecture, László Lovász settled out a new lower bound for the chromatic number. He showed that if neighborhood complex $\mathcal{N}(G)$ of a graph $G$ is topologically $k$-connected, then its chromatic number is at least $k+3$. Then he completed his proof by showing that this bound is tight for the Kneser graph. However, there are some graphs where this bound is not useful at all, even comparing by the obvious bound; the clique number. For instance, if a graph contains no complete bipartite graph ${\mathcal{K}}_{l,m}$, then its Lovász's bound is at most $l+m-1$. But, it can have an arbitrarily large chromatic number. In this note, we present new graphs showing that the gaps between the chromatic number, the clique number, and the Lovász bound can be arbitrarily large. More precisely, for given positive integers $l,m$ and $2\le p\le q$, we construct a connected graph which contains a copy of ${\mathcal{K}}_{l,m}$, and its chromatic number, clique number, and Lovász's bound are $q$, $p$, and $3$, respectively.