Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2412.20001 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914028290310144 |
|---|---|
| author | Kuffner, Luis Naserasr, Reza Wang, Lujia Yu, Xiaowei Zhou, Huan Zhu, Xuding |
| author_facet | Kuffner, Luis Naserasr, Reza Wang, Lujia Yu, Xiaowei Zhou, Huan Zhu, Xuding |
| contents | 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 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20001 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Colouring signed analogues of Kneser, Schrijver, and Borsuk graphs Kuffner, Luis Naserasr, Reza Wang, Lujia Yu, Xiaowei Zhou, Huan Zhu, Xuding Combinatorics 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 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. |
| title | Colouring signed analogues of Kneser, Schrijver, and Borsuk graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2412.20001 |