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

Seog-Jin Kim, Boram Park

Published 2013-05-12Version 1

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)) \leq 4k+2$, and Chen, Lih, and Wu \cite{2009CLW} showed that $\chi(K^2(2k+1,k)) \leq 3k+2$ for $k \geq 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)) \leq 2k+2$, if $ 2k +1 = 2^n -1$ for some positive integer $n$. Also we show that $\chi(K^2(2k+1,k)) \leq \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 \leq r \leq k-2$.