Skip to content
Log in

Author

Peter Bradshaw

View on Semantic Scholar

2 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Jul 2026

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, $\chi(G)$, satisfies $k\leq \chi(G)\leq 2k$. Fundamental results by Borodin from 1976 and Bollob\'as 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.

Peter Bradshaw, Alexandr V. Kostochka, Zimu Xiang · 0 citations
Open access Jul 2026

Flexible List Coloring of Graphs With Maximum Average Degree Less Than 3

In the flexible list coloring problem, we consider a graph and a color list assignment on , as well as a subset for which each has a preferred color . Our goal is to find a proper ‐coloring of such that for at least vertices . We say that is ‐flexibly ‐choosable if for every ‐size list assignment on and every subset of vertices with coloring preferences, has a proper ‐coloring that satisfies an proportion of these coloring preferences. Dvořák, Norin, and Postle [Journal of Graph Theory, 2019] asked whether every ‐degenerate graph is ‐flexibly ‐choosable for some constant . In this paper, we prove that there exists a constant such that every graph with maximum average degree less than 3 is ‐flexibly 3‐choosable, which gives a large class of 2‐degenerate graphs which are ‐flexibly ‐choosable. In particular, our results imply a theorem of Dvořák, Masařík, Musílek, and Pangrác [Journal of Graph Theory, 2020] stating that every planar graph of girth 6 is ‐flexibly 3‐choosable for some constant . To prove our result, we generalize the existing reducible subgraph framework traditionally used for flexible list coloring to allow reducible subgraphs of arbitrarily large order.

Richard Bi, Peter Bradshaw · 0 citations