Coloring of the square of Kneser graph $K(2k+r,k)$

Abstract

The Kneser graph $K(n,k)$ is the graph whose vertices are the $k$-element subsets of an $n$ elements set, with two vertices adjacent if they 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(n,k)$ is an interesting graph coloring problem, and is also related with intersecting family problem. The square of $K(2k,k)$ is a perfect matching and the square of $K(n,k)$ is the complete graph when $n\ge 3k-1$. Hence coloring of the square of $K(2k+1,k)$ has been studied as the first nontrivial case. In this paper, we focus on the question of determining $\chi (K^2(2k+r,k))$ for $r\ge 2$. Recently, Kim and Park \cite{KP2014} showed that $\chi (K^2(2k+1,k))\le 2k+2$ if $2k+1=2^t-1$ for some positive integer $t$. In this paper, we generalize the result by showing that for any integer $r$ with $1\le r\le k-2$, (a) $\chi (K^2(2k+r,k))\le (2k+r{)}^r$, if $2k+r=2^t$ for some integer $t$, and (b) $\chi (K^2(2k+r,k))\le (2k+r+1{)}^r$, if $2k+r=2^t-1$ for some integer $t$. On the other hand, it was showed in \cite{KP2014} that $\chi (K^2(2k+r,k))\le (r+2)(3k+\frac{3r+3}{2}{)}^r$ for $2\le r\le k-2$. We improve these bounds by showing that for any integer $r$ with $2\le r\le k-2$, we have $\chi (K^2(2k+r,k))\le 2{\left(\frac{9}{4}k+\frac{9(r+3)}{8}\right)}^r$. Our approach is also related with injective coloring and coloring of Johnson graph.