pith. sign in

arxiv: 1803.04342 · v2 · pith:XSUV3BQCnew · submitted 2018-03-12 · 🧮 math.CO

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

classification 🧮 math.CO
keywords numberpointschromaticcirculargraphcircleemphsubsets
0
0 comments X
read the original abstract

Let $n,k,r$ be positive integers with $n \geq rk$ and $r \geq 2$. Consider a circle $C$ with~$n$ points~$1,\ldots,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 $\binom{n-(r-1)k-1}{k-1}$, thereby strengthening a result by Talbot.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.