{
  "id": "2308.15853",
  "version": "v1",
  "published": "2023-08-30T08:39:13.000Z",
  "updated": "2023-08-30T08:39:13.000Z",
  "title": "Weak$^*$ degeneracy and weak$^*$ $k$-truncated-degree-degenerate graphs",
  "authors": [
    "Huan Zhou",
    "Jialu Zhu",
    "Xuding Zhu"
  ],
  "comment": "19 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "This paper introduces the concept of weak$^*$ degeneracy of a graph that shares many nice properties of degeneracy. We prove that for any $f: V(G) \\to \\mathbb{N}$, if $G$ is weak$^*$ $f$-degenerate, then $G$ is DP-$f$-paintable and $f$-AT. Hence the weak$^*$ degeneracy of $G$ is an upper bound for many colouring parameters, including the online DP-chromatic number and the Alon-Tarsi number. Let $k$ be a positive integer and let $f(v)=\\min\\{d_G(v), k\\}$ for each vertex $v$ of $G$. If $G$ is weak$^*$ $f$-degenerate (respectively, $f$-choosable), then we say $G$ is weak$^*$ $k$-truncated-degree--degenerate (respectively, $k$-truncated-degree-choosable). Richtor asked whether every 3-connected non-complete planar graph is $6$-truncated-degree-choosable. We construct a 3-connected non-complete planar graph which is not $7$-truncated-degree-choosable, so the answer to Richtor's question is negative even if 6 is replaced by 7. Then we prove that every 3-connected non-complete planar graph is weak$^*$ $16$-truncated-degree-degenerate (and hence $16$-truncated-degree-choosable). For an arbitrary proper minor closed family ${\\mathcal G}$ of graphs, let $s$ be the minimum integer such that $K_{s,t} \\notin \\mathcal{G}$ for some $t$. We prove that there is a constant $k$ such that every $s$-connected non-complete graph $G \\in {\\mathcal G}$ is weak$^*$ $k$-truncated-degree-degenerate. In particular, for any surface $\\Sigma$, there is a constant $k$ such that every 3-connected non-complete graph embeddable on $\\Sigma$ is weak$^*$ $k$-truncated-degree-degenerate.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-08-30T08:39:13.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "non-complete planar graph",
      "truncated-degree-degenerate graphs",
      "degeneracy",
      "non-complete graph",
      "online dp-chromatic number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}