DP vertex-arboricity of sparse graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.08584
curl -X POST /api/v1/records/arxiv/2607.08584/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.08584/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'