{
  "annotation_id": "7043e87f-83f4-47f6-bd8a-730176a07030",
  "date_created": "2026-03-02T18:02:30.930000Z",
  "date_modified": "2026-03-02T18:02:30.930000Z",
  "file_hash": "d723ae2469fc9578aefbbb021c091d637f787b9d9313a48931903bc627677e60",
  "private": false,
  "record": {
    "abstract": "We investigate the notion of quantum chromatic number of a graph, which is\nthe minimal number of colours necessary in a protocol in which two separated\nprovers can convince an interrogator with certainty that they have a colouring\nof the graph.\n  After discussing this notion from first principles, we go on to establish\nrelations with the clique number and orthogonal representations of the graph.\nWe also prove several general facts about this graph parameter and find large\nseparations between the clique number and the quantum chromatic number by\nlooking at random graphs.\n  Finally, we show that there can be no separation between classical and\nquantum chromatic number if the latter is 2, nor if it is 3 in a restricted\nquantum model; on the other hand, we exhibit a graph on 18 vertices and 44\nedges with chromatic number 5 and quantum chromatic number 4.",
    "arxiv_id": "quant-ph/0608016",
    "authors": [
      "Peter J. Cameron",
      "Ashley Montanaro",
      "Michael W. Newman",
      "Simone Severini",
      "Andreas Winter"
    ],
    "categories": [
      "quant-ph",
      "math.CO"
    ],
    "journal_ref": "Electronic Journal of Combinatorics 14(1), 2007",
    "title": "On the quantum chromatic number of a graph",
    "url": "https://arxiv.org/abs/quant-ph/0608016"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "e796e457-5c14-4731-a0af-b193521c1b1b",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}