{"id":"arxiv/2607.08584","url":"https://arxiv.org/abs/2607.08584","tags":["math.CO"],"score":0,"title":"DP vertex-arboricity of sparse graphs","domain":"math.CO","source":"arxiv","authors":["Peter Bradshaw","Alexandr Kostochka","Zimu Xiang"],"reviews":0,"subject":"math.CO","summary":"The vertex arboricity $\\mathrm{va}(G)$ of a multigraph $G$ is the minimum number $k$ for which $V(G)$ can be partitioned into $k$ subsets, each of which induces an acyclic subgraph of $G$. By definition, if $\\mathrm{va}(G)= k$, then the chromatic number, $χ(G)$, satisfies $k\\leq χ(G)\\leq 2k$. Fundamental results by Borodin from 1976 and Bollobás and Manvel from 1979 imply an analog of Gallai's lower bound on the number of edges in a $(2k-1)$-critical graph. We consider a slight generalization of vertex arboricity in the setting of DP-coloring. Using this framework, we derive lower bounds on…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-09","reactions":{}}