{
  "id": "2211.16728",
  "version": "v1",
  "published": "2022-11-30T04:24:09.000Z",
  "updated": "2022-11-30T04:24:09.000Z",
  "title": "On a problem of Cranston and Mahmoud",
  "authors": [
    "Dibyayan Chakraborty",
    "Carl Feghali"
  ],
  "comment": "6 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A classical theorem of Gallai states that in every graph that is critical for $k$-colorings, the vertices of degree $k - 1$ induce a tree-like graph whose blocks are either complete graphs or cycles of odd length. Borodin and, independently, Erd\\H{o}s et al. provided a well-known generalization of Gallai's Theorem to list colorings, where the list at each vertex has the same number of available colors as the degree of that vertex. In this paper, we obtain an analogous result for Kempe equivalence of list colorings, making substantial progress towards a problem of Cranston and Mahmoud.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-11-30T04:24:09.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "list colorings",
      "complete graphs",
      "gallai states",
      "well-known generalization",
      "gallais theorem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}