{
  "id": "2407.05730",
  "version": "v1",
  "published": "2024-07-08T08:34:21.000Z",
  "updated": "2024-07-08T08:34:21.000Z",
  "title": "Multi-Colouring of Kneser Graphs: Notes on Stahl's Conjecture",
  "authors": [
    "Jan van den Heuvel",
    "Xinyi Xu"
  ],
  "comment": "17 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "If a graph is $n$-colourable, then it obviously is $n'$-colourable for any $n'\\ge n$. But the situation is not so clear when we consider multi-colourings of graphs. A 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. In this note 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-07-08T08:34:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "kneser graphs",
      "stahls conjecture",
      "adjacent vertices receive disjoint subsets",
      "colourable",
      "question regarding multi-colourings"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}