On the circular chromatic number of a subgraph of the Kneser graph

Abstract

Let $n,k,r$ be positive integers with $n\ge rk$ and $r\ge 2$. Consider a circle $C$ with~$n$ points~$1,\dots ,n$ in clockwise order. The $r$-stable \emph{interlacing graph} ${\text{IG}}_{n,k}^{(r)}$ is the graph with vertices corresponding to $k$-subsets $S$ of $\{1,...,n\}$ such that any two distinct points in~$S$ have distance at least~$r$ around the circle, and edges between~$k$-subsets $P$ and $Q$ if they \emph{interlace}: after removing the points in~$P$ from $C$, the points in~$Q$ are in different connected components. In this paper we prove that the circular chromatic number of ${\text{IG}}_{n,k}^{(r)}$ is equal to $n/k$ (hence the chromatic number is $\lceil n/k\rceil$) and that its circular clique number is also $n/k$. Furthermore, we show that its independence number is $\left(\genfrac{}{}{0ex}{}{n-(r-1)k-1}{k-1}\right)$, thereby strengthening a result by Talbot.

Version 2 differs significantly from version 1. The main result, Theorem 1.1, and Theorem 1.3 have been generalized substantially. Theorem 1.4 is new. 12 pages