{
  "id": "2406.02792",
  "version": "v1",
  "published": "2024-06-04T21:32:35.000Z",
  "updated": "2024-06-04T21:32:35.000Z",
  "title": "Weak Degeneracy of Planar Graphs",
  "authors": [
    "Anton Bernshteyn",
    "Eugene Lee",
    "Evelyne Smith-Roberge"
  ],
  "comment": "12 pages, 3 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "The weak degeneracy of a graph $G$ is a numerical parameter that was recently introduced by the first two authors with the aim of understanding the power of greedy algorithms for graph coloring. Every $d$-degenerate graph is weakly $d$-degenerate, but the converse is not true in general (for example, all connected $d$-regular graphs except cycles and cliques are weakly $(d-1)$-degenerate). If $G$ is weakly $d$-degenerate, then the list-chromatic number of $G$ is at most $d+1$, and the same upper bound holds for various other parameters such as the DP-chromatic number and the paint number. Here we rectify a mistake in a paper of the first two authors and give a correct proof that planar graphs are weakly $4$-degenerate, strengthening the famous result of Thomassen that planar graphs are $5$-list-colorable.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-06-04T21:32:35.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "planar graphs",
      "weak degeneracy",
      "upper bound holds",
      "correct proof",
      "regular graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}