Improved bounds on the chromatic numbers of the square of Kneser graphs

Abstract

The Kneser graph $K(n,k)$ is the graph whose vertices are the $k$-elements subsets of an $n$-element set, with two vertices adjacent if the sets are disjoint. The square $G^2$ of a graph $G$ is the graph defined on $V(G)$ such that two vertices $u$ and $v$ are adjacent in $G^2$ if the distance between $u$ and $v$ in $G$ is at most 2. Determining the chromatic number of the square of the Kneser graph $K(2k+1,k)$ is an interesting problem, but not much progress has been made. Kim and Nakprasit \cite{2004KN} showed that $\chi (K^2(2k+1,k))\le 4k+2$, and Chen, Lih, and Wu \cite{2009CLW} showed that $\chi (K^2(2k+1,k))\le 3k+2$ for $k\ge 3$. In this paper, we give improved upper bounds on $\chi (K^2(2k+1,k))$. We show that $\chi (K^2(2k+1,k))\le 2k+2$, if $2k+1=2^n-1$ for some positive integer $n$. Also we show that $\chi (K^2(2k+1,k))\le \frac{8}{3}k+\frac{20}{3}$ for every integer $k\ge 2$. In addition to giving improved upper bounds, our proof is concise and can be easily understood by readers while the proof in \cite{2009CLW} is very complicated. Moreover, we show that $\chi (K^2(2k+r,k))=\Theta (k^r)$ for each integer $2\le r\le k-2$.