Peter Bradshaw
About Me
I am a postdoctoral researcher employed at the University of Illinois Urbana-Champaign working with Alexandr Kostochka. I completed my PhD at Simon Fraser University under Bojan Mohar and Ladislav Stacho in December, 2022.
My research in graph theory so far has focused mainly on graph coloring and games on graphs. However, my main research interests are the techniques I have used to approach these topics: graph decompositions, probabilistic techniques, and algebraic structures.
Graph decompositions
How many colors are necessary to color the Cartesian product of two graphs, even with interference from an adversary? Can a graph be list colored even while satisfying a certain number of coloring preferences at its vertices? Can an outerplanar graph always be colored so that no vertex can guess its own color correctly? These are all problems that I have approached by decomposing a graph into more well-behaved substructures. While many graphs appear difficult to attack directly, they become much easier to work with after they are broken down into smaller, simpler pieces.
Probabilistic techniques
Can a graph G be colored with k colors so that every two-colored subgraph is planar? Can G be colored so that a specific forbidden color pair is avoided at every edge? If G is a random edge-colored graph, does a rainbow path connect every vertex pair? These are the types of questions that I attack with the probabilistic method. To answer questions for fixed graphs, I use randomized approaches including the Lovász Local Lemma and entropy compression, and to answer questions for random graphs, I use a variety of probabilistic tools.
Algebraic structures
How many cops are necessary to capture a robber on a Cayley graph over an abelian group? Which graphs on n vertices require Θ(√n) cops to capture a robber? When is the covering graph of a reflexive tree lifted over a cyclic group Hamiltonian? These are all questions that I have investigated that have algebra at their core or that can be attacked with algebra. To answer these questions, I use a combination of tools from group theory, finite fields, and traditional graph theory.
Publications and preprints
26. A lower bound on the number of edges in DP-critical graphs. II. Four colors
With Ilkyoo Choi, Alexandr Kostochka, and Jingwei Xu. Submitted (2024).
25. A lower bound on the number of edges in DP-critical graphs
With Ilkyoo Choi, Alexandr Kostochka, and Jingwei Xu. Submitted (2024).
24. Bipartite graphs are (4/5−ε)Δ/log Δ-choosable
With Bojan Mohar and Ladislav Stacho. Submitted (2024).
23. Graphs of maximum average degree less than 11/3 are flexibly 4-choosable
With Richard Bi. Submitted (2024).
22. Cornering Robots to Synchronize a DFA.
with Alexander Clow and Ladislav Stacho. In revision for TCS (2024).
21. Paintability of r-chromatic graphs.
With Jinghan A. Zeng. Submitted (2024).
20. Flexibility of graphs with maximum average degree less than 3.
With Richard Bi. (2024).
19. List-avoiding orientations.
With Yaobin Chen, Hao Ma, Bojan Mohar, and Hehui Wu. Combinatorica. (2024).
18. Injective edge colorings of degenerate graphs and the oriented chromatic number.
With Alexander Clow and Jingwei Xu. Submitted. (2023)
17. Fractional colorings of partial t-trees with no large cliques.
Submitted. (2023)
16. Rainbow spanning trees in random subgraphs of dense regular graphs.
Discrete Mathematics. (2023)
15. Single-conflict colorings of degenerate graphs.
With Tomáš Masařík. Journal of Graph Theory. (2023)
14. Cooperative colorings of forests.
Elec. J. Comb. (2022)
13. Separating the online and offline DP-chromatic numbers.
Elec. J. Comb. (2022)
12. Hamiltonicity of covering graphs of trees.
With Zhilin Ge and Ladislav Stacho. Submitted. (2022)
11. On the hat guessing number of a planar graph class.
Journal of Comb. Theory, Ser. B (2021).
10. A rainbow connectivity threshold for random graph families.
With Bojan Mohar. Eurocomb (2021).
9. Robust Connectivity of Graphs on Surfaces.
With Tomáš Masařík, Jana Novotná, and Ladislav Stacho. SIDMA (2021).
8. From one to many rainbow Hamiltonian cycles.
With Kevin Halasz and Ladislav Stacho. Graphs and Comb. (2021).
7. Graph colorings with restricted bicolored subgraphs: II. The graph coloring game.
J. Graph Theory (2021).
6. Flexible List Colorings in Graphs with Special Degeneracy Conditions.
With Tomáš Masařík and Ladislav Stacho. J. Graph Theory (2020).
5. A note on the connected game coloring number.
Disc. App. Math. (2020).
4. Cops and robbers on graphs of high girth.
With Seyyed Aliasghar Hosseini, Bojan Mohar, and Stacho. J. Graph Theory (2021).
3. Transversals and bipancyclicity in bipartite graph families.
Elec. J. Comb. (2021).
2. Cops and robbers on directed and undirected abelian Cayley graphs.
With Seyyed Aliasghar Hosseini and Jérémie Turcotte. European J. Comb. (2021).
1. A proof of Meyniel’s conjecture for abelian Cayley graphs.
Discrete Mathematics (2019).
CV
Education
PhD., Mathematics, Simon Fraser University, GPA: 4.17/4.33
-
Thesis: Graph colorings with local restrictions, advised by Bojan Mohar and Ladislav Stacho
MSc., Mathematics, Simon Fraser University, GPA: 4.13/4.33
-
Thesis: Cops and robbers on Cayley graphs and embedded graphs, advised by Ladislav Stacho
B.S., Mathematics, University of Kansas, GPA: 3.82/4.00
Sep 2020 - Dec 2022
Sep 2018 - Aug 2020
2012 - 2016
Employment
Postdoctoral Researcher, University of Illinois Urbana-Champaign
-
Working under Alexandr Kostochka
Jan 2023 - Present