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

The Kneser graph K(n,k)K(n,k) is the graph whose vertices are the kk-element subsets of an nn-elements set, with two vertices adjacent if the sets are disjoint. The square G2G2 of a graph GG is the graph defined on V(G)V(G) such that two vertices uu and vv are adjacent in G2G2 if the distance between uu and vv in GG is at most 2. Determining the chromatic number of the square of the Kneser graph K(2k+1,k)K(2k+1,k) is an interesting problem, but not much progress has been made. Kim and Nakprasit (2004) showed that χ(K2(2k+1,k))≤4k+2χ(K2(2k+1,k))≤4k+2, and Chen, Lih, and Wu (2009) showed that χ(K2(2k+1,k))≤3k+2χ(K2(2k+1,k))≤3k+2 for k≥3k≥3. In this paper, we give improved upper bounds on χ(K2(2k+1,k))χ(K2(2k+1,k)). We show that χ(K2(2k+1,k))≤2k+2χ(K2(2k+1,k))≤2k+2, if 2k+1=2n−12k+1=2n−1 for some positive integer nn. Also we show that χ(K2(2k+1,k))≤83k+203 for every integer k≥2k≥2. In addition to giving improved upper bounds, our proof is concise and can be easily understood by readers while the proof in Chen et al. (2009) is very complicated. Moreover, we show that χ(K2(2k+r,k))=Θ(kr)χ(K2(2k+r,k))=Θ(kr) for each integer 2≤r≤k−22≤r≤k−2.