PreprintCC BY-NC-SA 4.0arXiv
DP vertex-arboricity of sparse graphs
Abstract
The vertex arboricity 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 va(G)= k, then the chromatic number, χ(G), satisfies k≤ χ(G)≤ 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 the number of edges in graphs critical for vertex arboricity and for list arboricity that are better than Gallai's bound, along with similar bounds in our DP-setting.
Related
- Arboricity and Simplicial Geometric Category of Wedges and Joins of Graphs
- Linear arboricity conjecture for infinite graphs
- Two-point concentration for graph classes admitting sparse vertex deletion
- Multi-Way Expansion, Laplacian Gaps, and Imprimitivity in Vertex-Transitive Graphs
- Enumeration of small vertex-transitive directed strongly regular graphs
BibTeX
@misc{bradshaw2026vertexarboricity,
title = {{DP vertex-arboricity of sparse graphs}},
author = {Peter Bradshaw and Alexandr Kostochka and Zimu Xiang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.08584},
eprint = {2607.08584},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.08584},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - DP vertex-arboricity of sparse graphs
AU - Peter Bradshaw
AU - Alexandr Kostochka
AU - Zimu Xiang
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2607.08584
UR - https://arxiv.org/abs/2607.08584
AB - The vertex arboricity 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 va(G)= k, then the chromatic number, χ(G), satisfies k≤ χ(G)≤ 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 the number of edges in graphs critical for vertex arboricity and for list arboricity that are better than Gallai's bound, along with similar bounds in our DP-setting.
ER -