Peter Bradshaw

activity

20232026

collaborators

17 papers

math.CO2026

Density of list- and correspondence-critical graphs

Peter Bradshaw

A graph $G$ is list $k$ -critical if $G$ is not $(k - 1)$ -list-colorable, but every proper subgraph of $G$ is $(k - 1)$ -list-colorable. In this paper, we study the function $f_{\ell}(n,…

math.CO2026

DP vertex-arboricity of sparse graphs

Peter Bradshaw, Alexandr Kostochka, Zimu Xiang

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…

math.CO2026

The strong chromatic index of $K_{t, t}$ -free graphs

Richard Bi, Peter Bradshaw, Abhishek Dhawan +1

A strong edge coloring of a graph $G$ is an edge coloring $ϕ : E (G) \to N$ such that each color class forms an induced matching in $G$ . The strong chromatic index…

math.CO2025

Choosability of multipartite hypergraphs

Peter Bradshaw, Abhishek Dhawan, Nhi Dinh +2

A $k$ -uniform hypergraph (or $k$ -graph) $H = (V, E)$ is $k$ -partite if $V$ can be partitioned into $k$ sets $V_{1}, \dots, V_{k}$ such that each edge in $E$ contains precisely one ver…

math.CO2025

Density of rainbow triangles and properly colored $K_{4}$ 's

József Balogh, Peter Bradshaw, Ramon I. Garcia +1

We establish a sharp upper bound on the number of properly $3$ -edge-colored $K_{4}$ 's in graphs with $R$ red, $G$ green and $B$ blue edges. We give a computer-free flag-algebra proof…

math.CO2025

Flexible DP 3-coloring of sparse multigraphs

Peter Bradshaw, Ilkyoo Choi, Alexandr Kostochka

A \emph{request} on a graph assigns a preferred color to a subset of the vertices. A graph $G$ is \emph{ $ε$ -flexibly $k$ -choosable} if for every $k$ -list assignment $L$ and every r…

math.CO2025

Toward Vu's conjecture

Peter Bradshaw, Abhishek Dhawan, Abhishek Methuku +1

In 2002, Vu conjectured that graphs of maximum degree $Δ$ and maximum codegree at most $ζ Δ$ have chromatic number at most $(ζ + o (1)) Δ$ . Despite its importance, the conjecture has re…

math.CO2024

Chip games and multipartite graph paintability

Peter Bradshaw, Tianyue Cao, Atlas Chen +6

We study the paintability, an on-line version of choosability, of complete multipartite graphs. We do this by considering an equivalent chip game introduced by Duraj, Gutowski, and…

math.CO2024

Strong parity edge-colorings of graphs

Peter Bradshaw, Sergey Norin, Douglas B. West

An edge-coloring of a graph $G$ assigns a color to each edge of $G$ . An edge-coloring is a parity edge-coloring if for each path $P$ in $G$ , it uses some color on an odd number of…

math.CO2024

A lower bound on the number of edges in DP-critical graphs. II. Four colors

Peter Bradshaw, Ilkyoo Choi, Alexandr Kostochka +1

A graph $G$ is $k$ -critical (list $k$ -critical, DP $k$ -critical) if $χ (G) = k$ ( $χ_{ℓ} (G) = k$ , $χ_{DP} (G) = k$ ) and for every proper subgraph $G^{'}$ of $G$ , $χ (G^{'}) < k$ ($χ_\ell(…

math.CO2024

Bipartite graphs are $(\frac{4}{5} - ε) \frac{Δ}{l o g Δ}$ -choosable

Peter Bradshaw, Bojan Mohar, Ladislav Stacho

Alon and Krivelevich conjectured that if $G$ is a bipartite graph of maximum degree $Δ$ , then the choosability (or list chromatic number) of $G$ satisfies $χ_{\ell}(G) = O \left (…

math.CO2024

A lower bound on the number of edges in DP-critical graphs

Peter Bradshaw, Ilkyoo Choi, Alexandr Kostochka +1

math.CO2024

Graphs of maximum average degree less than $\frac{11}{3}$ are flexibly $4$ -choosable

Richard Bi, Peter Bradshaw

We consider the flexible list coloring problem, in which we have a graph $G$ , a color list assignment $L : V (G) \to 2^{N}$ , and a set $U \subseteq V (G)$ of vertices s…

cs.FL2024

A cornering strategy for synchronizing a DFA

Peter Bradshaw, Alexander Clow, Ladislav Stacho

This paper considers the existence of short synchronizing words in deterministic finite automata (DFAs). We define two general strategies for generating synchronizing words, and we…

math.CO2024

Paintability of $r$ -chromatic graphs

Peter Bradshaw, Jinghan A Zeng

The online list coloring game is a two-player graph-coloring game played on a graph $G$ as follows. On each turn, a Lister reveals a new color $c$ at some subset $S \subseteq V (G)$ …

math.CO2023

Flexible list coloring of graphs with maximum average degree less than $3$

Richard Bi, Peter Bradshaw

In the flexible list coloring problem, we consider a graph $G$ and a color list assignment $L$ on $G$ , as well as a subset $U \subseteq V (G)$ for which each $u \in U$ has a preferr…

math.CO2023

Fractional colorings of partial $t$ -trees with no large clique

Peter Bradshaw

Dvořák and Kawarabayashi [European Journal of Combinatorics, 2017] asked, what is the largest chromatic number attainable by a graph of treewidth $t$ with no $K_{r}$ subgraph? In thi…

Density of list- and correspondence-critical graphs

DP vertex-arboricity of sparse graphs

The strong chromatic index of Kt,t​-free graphs

Choosability of multipartite hypergraphs

Density of rainbow triangles and properly colored K4​'s

Flexible DP 3-coloring of sparse multigraphs

Toward Vu's conjecture

Chip games and multipartite graph paintability

Strong parity edge-colorings of graphs

A lower bound on the number of edges in DP-critical graphs. II. Four colors

Bipartite graphs are (54​−ε)logΔΔ​-choosable

A lower bound on the number of edges in DP-critical graphs

Graphs of maximum average degree less than 311​ are flexibly 4-choosable

A cornering strategy for synchronizing a DFA

Paintability of r-chromatic graphs

Flexible list coloring of graphs with maximum average degree less than 3

Fractional colorings of partial t-trees with no large clique

The strong chromatic index of $K_{t, t}$ -free graphs

Density of rainbow triangles and properly colored $K_{4}$ 's

Bipartite graphs are $(\frac{4}{5} - ε) \frac{Δ}{l o g Δ}$ -choosable

Graphs of maximum average degree less than $\frac{11}{3}$ are flexibly $4$ -choosable

Paintability of $r$ -chromatic graphs

Flexible list coloring of graphs with maximum average degree less than $3$

Fractional colorings of partial $t$ -trees with no large clique