2024/12/28 by Kuffner, Luis, Naserasr, Reza, Wang, Lujia +3 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2412.20001
The Kneser signed graph \KS(n,k), k≤ n, is the graph whose vertices are signed k-subsets of [n] (i.e. k-subsets S of \ ± 1, ± 2, …, ± n\ such that S∩ (-S)=∅). Two vertices A and B are adjacent with a positive edge if A∩ (-B)=∅ and with a negative edge if A∩ B=∅. 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 they form vertex-critical subgraphs of \KS(n,k) with respect to balanced colouring. Further connection to topological methods, in particular, connection to Borsuk signed graphs is also considered.