{
  "id": "2403.11888",
  "version": "v3",
  "published": "2024-03-18T15:43:19.000Z",
  "updated": "2024-07-04T22:25:14.000Z",
  "title": "Paintability of $r$-chromatic graphs",
  "authors": [
    "Peter Bradshaw",
    "Jinghan A Zeng"
  ],
  "comment": "13 pages, a terminology error was corrected",
  "categories": [
    "math.CO"
  ],
  "abstract": "The paintability of a graph is a coloring parameter defined in terms of an online list coloring game. In this paper we ask, what is the paintability of a graph $G$ of maximum degree $\\Delta$ and chromatic number $r$? By considering the Alon-Tarsi number of $G$, we prove that the paintability of $G$ is at most $\\left(1 - \\frac{1}{4r+1} \\right ) \\Delta + 2$. We also consider the DP-paintability of $G$, which is defined in terms of an online DP-coloring game. By considering the strict type $3$ degeneracy parameter recently introduced by Zhou, Zhu, and Zhu, we show that when $r$ is fixed and $\\Delta$ is sufficiently large, the DP-paintability of $G$ is at most $\\Delta - \\Omega( \\sqrt{\\Delta \\log \\Delta})$.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2024-07-04T22:25:14.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C15"
    ],
    "keywords": [
      "chromatic graphs",
      "online list coloring game",
      "degeneracy parameter",
      "maximum degree",
      "strict type"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}