I am a postdoctoral researcher at University of Illinois Urbana-Champaign working with Alexandr Kostochka and Jozsef Balogh in graph theory.

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. My main interest, however, is in learning interesting techniques to solve hard problems. I mainly use the following techniques: probabilistic methods, recursive decompositions, and algebraic structures.

My Erdős number is 2 (1, 2 or 1, 2).

Probabilistic methods

The “nibble method” is a random graph-coloring algorithm in which one colors a graph in steps by choosing a small random subgraph on each step and giving it a random coloring. I have used the nibble method to attack conjectures of Vu and of Erdős and Nešetřil. I have also combined randomized algorithms with the Lovász local Lemma to attack problems related to injective and strong edge-coloring, single-conflict coloring, and weak degeneracy. Probabilistic and randomized approaches are currently one of my main interests, and I hope to learn more techniques in the future.

Recursive decompositions

One powerful technique in graph coloring is showing that every instance of a certain type of coloring problem can be reduced to a smaller, easier problem. This technique often leads to ways of decomposing a graph into small pieces that allow for a recursive algorithm to color the graph in polynomial time. I have applied recursive approaches, along with similar tools such as the powerful potential method of Kostochka and Yancey, to problems of critical graph density in the list, correspondence, and flexible settings, as well as fractional graph coloring and adversarial graph coloring.

Algebraic tools

Graph coloring problems, and more generally graph labelling problems, often have deep connections with algebraic structures. For example, the proper colorings of a graph with prescribed color lists can be characterized as points at which a certain polynomial has a nonzero evaluation. Similarly, parameters such as chromatic number are often closely related to the eigenvalues of a graph’s adjacency matrix. In previous work, I have used such polynomial methods to attack graph labelling problems that seek an orientation satisfying given local conditions. Furthermore, in ongoing work, I relate the eigenvalues of a graph’s adjacency matrix with properties such as its matching number and strong chromatic index.

CV

Here is a copy of my CV (last updated in October, 2025).

Publications and preprints

30. Flexible DP 3-coloring of sparse multigraphs

With Ilkyoo Choi and Alexandr Kostochka. Submitted (2025).

29. Toward Vu’s conjecture

With Abhishek Dhawan, Abhishek Methuku, and Michael Wigal. Submitted (2025)

28. Strong Parity Edge-Colorings of Graphs

With Sergey Norin and Douglas West. Submitted (2025).

27. Chip games and multipartite graph paintability

With Tianyue Cao, Atlas Chen, Braden Dean, Siyu Gan, Ramon I. Garcia, Amit Krishnaiyer, Grace McCourt, Arvind Murty. Submitted (2025, collaboration with undergraduate students)

26. A cornering strategy for synchronizing a DFA

With Alexander Clow and Ladislav Stacho. In revision for Theoretical Computer Science (2025).

25. Paintability of r-chromatic graphs

With Jinghan A. Zeng. Discrete Mathematics. (2025, collaboration with undergraduate student).

24. Injective edge colorings of degenerate graphs and the oriented chromatic number.

With Alexander Clow and Jingwei Xu. European Journal of Combinatorics (2025)

23. Fractional colorings of partial t-trees with no large cliques.

Discrete Mathematics (2025)

22. Flexibility of graphs with maximum average degree less than 3

With Richard Bi. Accepted to Journal of Graph Theory, in revision. (2024+, collaboration with undergraduate student).

21. 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).