Peter Bradshaw

activity

20192023

most citedCops and robbers on directed and undirected abelian Cayley graphs

10 citations · 34 across the 20 of their papers we have counts for

collaborators

Showing math.COShow all

21 papers · 1 filter

math.CO2023

Injective edge colorings of degenerate graphs and the oriented chromatic number

Peter Bradshaw, Alexander Clow, Jingwei Xu

Given a graph $G$ , an injective edge-coloring of $G$ is a function $ψ : E (G) \to N$ such that if $ψ (e) = ψ (e^{'})$ , then no third edge joins an endpoint of $e$ and an en…

math.CO2022★ 2 cited

List-avoiding orientations

Peter Bradshaw, Yaobin Chen, Hao Ma +2

Given a graph $G$ with a set $F (v)$ of forbidden values at each $v \in V (G)$ , an $F$ -avoiding orientation of $G$ is an orientation in which $d e g^{+} (v) \neq \in F (v)$ for each vertex…

math.CO2022

Hamiltonicity of covering graphs of trees

Peter Bradshaw, Zhilin Ge, Ladislav Stacho

In this paper, we consider covering graphs obtained by lifting a tree with a loop at each vertex as a voltage graph over a cyclic group. We generalize a tool of Hell, Nishiyama, an…

math.CO2022

Separating the online and offline DP-chromatic numbers

Peter Bradshaw

The DP-coloring problem is a generalization of the list-coloring problem in which the goal is to find an independent transversal in a certain topological cover of a graph $G$ . In t…

math.CO2022

Cooperative colorings of forests

Peter Bradshaw

Given a family $G$ of graphs spanning a common vertex $V$ , a cooperative coloring of $G$ is a collection of one independent set from each graph of $G$ su…

math.CO2021

Single-conflict colorings of degenerate graphs

Peter Bradshaw, Tomáš Masařík

We consider the single-conflict coloring problem, a graph coloring problem in which each edge of a graph receives a forbidden ordered color pair. The task is to find a vertex color…

math.CO2021

Hat guessing number and guaranteed subgraphs

Peter Bradshaw

The hat guessing number of a graph is a parameter related to the hat guessing game for graphs introduced by Winkler. In this paper, we show that graphs of sufficiently large hat gu…

math.CO2021

A rainbow connectivity threshold for random graph families

Peter Bradshaw, Bojan Mohar

Given a family $G$ of graphs on a common vertex set $X$ , we say that $G$ is rainbow connected if for every vertex pair $u, v \in X$ , there exists a path from $u$ t…

math.CO2021★ 4 cited

On the hat guessing number of a planar graph class

Peter Bradshaw

The hat guessing number is a graph invariant based on a hat guessing game introduced by Winkler. Using a new vertex decomposition argument involving an edge density theorem of Erdő…

math.CO2021★ 2 cited

Robust Connectivity of Graphs on Surfaces

Peter Bradshaw, Tomáš Masařík, Jana Novotná +1

Let $Λ (T)$ denote the set of leaves in a tree $T$ . One natural problem is to look for a spanning tree $T$ of a given graph $G$ such that $Λ (T)$ is as large as possible. This proble…

math.CO2021

From one to many rainbow Hamiltonian cycles

Peter Bradshaw, Kevin Halasz, Ladislav Stacho

Given a graph $G$ and a family $G = {G_{1}, \dots, G_{n}}$ of subgraphs of $G$ , a transversal of $G$ is a pair $(T, ϕ)$ such that $T \subseteq E (G)$ and $ϕ: T \righ…

math.CO2021★ 1 cited

Rainbow spanning trees in random subgraphs of dense regular graphs

Peter Bradshaw

We consider the following random model for edge-colored graphs. A graph $G$ on $n$ vertices is fixed, and a random subgraph $G_{p}$ is chosen by letting each edge of $G$ remain indep…

math.CO2020

An Incidence Result for Well-Spaced Atoms in all Dimensions

Peter Bradshaw

We prove an incidence result counting the $k$ -rich $δ$ -tubes induced by a well-spaced set of $δ$ -atoms. Our result coincides with the bound that would be heuristically predicted by…

math.CO2020

Graph colorings with restricted bicolored subgraphs: II. The graph coloring game

Peter Bradshaw

We consider the graph coloring game, a game in which two players take turns properly coloring the vertices of a graph, with one player attempting to complete a proper coloring, and…

math.CO2020★ 6 cited

Graph colorings with restricted bicolored subgraphs: I. Acyclic, star, and treewidth colorings

Peter Bradshaw

We show that for any fixed integer $m \geq 1$ , a graph of maximum degree $Δ$ has a coloring with $O (Δ^{(m + 1) / m})$ colors in which every connected bicolored subgraph contains at mos…

math.CO2020

A note on the connected game coloring number

Peter Bradshaw

We consider the \emph{connected game coloring number} of a graph, introduced by Charpentier et al. as a game theoretic graph parameter that measures the degeneracy of a graph with…

math.CO2020★ 4 cited

Flexible List Colorings in Graphs with Special Degeneracy Conditions

Peter Bradshaw, Tomáš Masařík, Ladislav Stacho

For a given $ε > 0$ , we say that a graph $G$ is $ε$ -flexibly $k$ -choosable if the following holds: for any assignment $L$ of color lists of size $k$ on $V (G)$ ,…

math.CO2020★ 1 cited

On the cop number of graphs of high girth

Peter Bradshaw, Seyyed Aliasghar Hosseini, Bojan Mohar +1

We establish a lower bound for the cop number of graphs of high girth in terms of the minimum degree, and more generally, in terms of a certain growth condition. We show, in partic…

math.CO2020

Transversals and bipancyclicity in bipartite graph families

Peter Bradshaw

A bipartite graph is called bipancyclic if it contains cycles of every even length from four up to the number of vertices in the graph. A theorem of Schmeichel and Mitchem states t…

math.CO2019★ 4 cited

Surrounding cops and robbers on graphs of bounded genus

Peter Bradshaw, Seyyed Aliasghar Hosseini

We consider a surrounding variant of cops and robbers on graphs of bounded genus. We obtain bounds on the number of cops required to surround a robber on planar graphs, toroidal gr…

math.CO2019★ 10 cited

Cops and robbers on directed and undirected abelian Cayley graphs

Peter Bradshaw, Seyyed Aliasghar Hosseini, Jérémie Turcotte

We show that the cop number of directed and undirected Cayley graphs on abelian groups has an upper bound of the form of $O (n)$ , where $n$ is the number of vertices, by intr…