Peter Bradshaw

activity

20232026

collaborators

Showing 2024Show all

8 papers · 1 filter

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)$ …

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

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