Paperlane

no. 15 · Monday 16 November 2026

Colouring signed analogues of Kneser, Schrijver, and Borsuk graphs

Luis Kuffner, Reza Naserasr, Lujia Wang, Xiaowei Yu, Huan Zhou and Xuding Zhu

math.CO · v4

Abstract

The Kneser signed graph $\KS(n,k)$, $k\leq n$, is the graph whose vertices are signed $k$-subsets of $[n]$ (i.e. $k$-subsets $S$ of $\{ \pm 1, \pm 2, \ldots, \pm n\}$ such that $S\cap (-S)=\emptyset$). Two vertices $A$ and $B$ are adjacent with a positive edge if $A\cap (-B)=\emptyset$ and with a negative edge if $A\cap B=\emptyset$. We prove that the balanced chromatic number of $\KS(n,k)$ is $n-k+1$. We then introduce the signed analogue of Schrijver graphs and show that choosing one representative from each antipodal pair of alternating signed $k$-sets gives a vertex-critical subgraph of $\KS(n,k)$ with respect to balanced colouring. For the Borsuk signed graph on $S^d$, we obtain balanced chromatic number $d+1$ for sufficiently small distance parameter and relate this equality to antipodal covers of the sphere. On $S^2$, spherical and projective covering bounds give three, four and six as the first successive values of the balanced chromatic number.

fields
Combinatorics
pdf ↗ page arXiv:2412.20001 ↗