Multi-Colouring of Kneser Graphs: Notes on Stahl's Conjecture
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913641984425984 |
|---|---|
| author | Heuvel, Jan van den Xu, Xinyi |
| author_facet | Heuvel, Jan van den Xu, Xinyi |
| contents | A (finite, undirected) graph is $(n,k)$-colourable if we can assign each vertex a $k$-subset of $\{1,2,\ldots,n\}$ so that adjacent vertices receive disjoint subsets. We consider the following problem: if a graph is $(n,k)$-colourable, then for what pairs $(n',k')$ is it also $(n',k')$-colourable? This question can be translated into a question regarding multi-colourings of Kneser graphs, for which Stahl formulated a conjecture in 1976. We present new results, strengthen existing results, and in particular present much simpler proofs of several known cases of the conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_05730 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Multi-Colouring of Kneser Graphs: Notes on Stahl's Conjecture Heuvel, Jan van den Xu, Xinyi Combinatorics 05C15 A (finite, undirected) graph is $(n,k)$-colourable if we can assign each vertex a $k$-subset of $\{1,2,\ldots,n\}$ so that adjacent vertices receive disjoint subsets. We consider the following problem: if a graph is $(n,k)$-colourable, then for what pairs $(n',k')$ is it also $(n',k')$-colourable? This question can be translated into a question regarding multi-colourings of Kneser graphs, for which Stahl formulated a conjecture in 1976. We present new results, strengthen existing results, and in particular present much simpler proofs of several known cases of the conjecture. |
| title | Multi-Colouring of Kneser Graphs: Notes on Stahl's Conjecture |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2407.05730 |