Source author record

Peter Bradshaw

Peter Bradshaw appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

What is connected

6works

2topics

3close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2024arXiv

Hat guessing number and guaranteed subgraphs

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 guessing number must contain arbitrary trees and arbitrarily long cycles as subgraphs. More precisely, for each tree $T$, there exists a value $N = N(T)$ such that every graph that does not contain $T$ as a subgraph has hat guessing number at most $N$, and for each integer $c$, there exists a value $N' = N'(c)$ such that every graph with no cycle of length greater than $c$ has hat guessing number at most $N'$.

preprint2023arXiv

Rainbow spanning trees in random subgraphs of dense regular graphs

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 independently with probability $p$. Then, each edge of $G_p$ is colored uniformly at random from the set $[n-1]$. A result of Frieze and McKay (Random Structures and Algorithms, 1994) implies that when $G = K_n$ and $p = (2 + ε) \frac{\log n}{n}$ for some constant $ε> 0$, then $G_p$ almost surely contains a rainbow spanning tree. In this paper, we show that if $G$ is a $d$-regular $Ω(n)$-edge-connected graph, then when $p = (2 + ε) \frac {\log n}{d}$ for some constant $ε> 0$, $G_p$ almost surely contains a rainbow spanning tree. Our main tool is a new edge-replacement method for rainbow forests.

preprint2022arXiv

Cooperative colorings of forests

Given a family $\mathcal G$ of graphs spanning a common vertex $V$, a cooperative coloring of $\mathcal G$ is a collection of one independent set from each graph of $\mathcal G$ such that the union of these independent sets equals $V$. We prove that when $d$ is large, there exists a family $\mathcal G$ of $(1+o(1)) \frac{\log d}{\log \log d}$ forests of maximum degree $d$ that admits no cooperative coloring, which significantly improves a result of Aharoni, Berger, Chudnovsky, Havet, and Jiang (Electronic Journal of Combinatorics, 2020). Our family $\mathcal G$ consists entirely of star forests, and we show that this value for $|\mathcal G|$ is asymptotically best possible in the case that $\mathcal G$ is a family of star forests.

preprint2021arXiv

Transversals and bipancyclicity in bipartite graph families

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 that for $n \geq 4$, every balanced bipartite graph on $2n$ vertices in which each vertex in one color class has degree greater than $\frac{n}{2}$ and each vertex in the other color class has degree at least $\frac{n}{2}$ is bipancyclic. We prove a generalization of this theorem in the setting of graph transversals. Namely, we show that given a family $\mathcal{G}$ of $2n$ bipartite graphs on a common set $X$ of $2n$ vertices with a common balanced bipartition, if each graph of $\mathcal G$ has minimum degree greater than $\frac{n}{2}$ in one color class and minimum degree at least $\frac{n}{2}$ in the other color class, then there exists a cycle on $X$ of each even length $4 \leq \ell \leq 2n$ that uses at most one edge from each graph of $\mathcal G$. We also show that given a family $\mathcal G$ of $n$ bipartite graphs on a common set $X$ of $2n$ vertices meeting the same degree conditions, there exists a perfect matching on $X$ that uses exactly one edge from each graph of $\mathcal G$.

preprint2020arXiv

A note on the connected game coloring number

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 respect to a certain two-player game played with an uncooperative adversary. We consider the connected game coloring number of graphs of bounded treedepth and of $k$-trees. In particular, we show that there exists an outerplanar $2$-tree with connected game coloring number of $5$, which answers a question from [C. Charpentier, H. Hocquard, E. Sopena, and X. Zhu. A connected version of the graph coloring game. \textit{Discrete Appl. Math.}, 2020].

preprint2020arXiv

On the cop number of graphs of high girth

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 particular, that the cop number of any graph with girth $g$ and minimum degree $δ$ is at least $\tfrac{1}{g}(δ- 1)^{\lfloor \frac{g-1}{4}\rfloor}$. We establish similar results for directed graphs. While exposing several reasons for conjecturing that the exponent $\tfrac{1}{4}g$ in this lower bound cannot be improved to $(\tfrac{1}{4}+\varepsilon)g$, we are also able to prove that it cannot be increased beyond $\frac{3}{8}g$. This is established by considering a certain family of Ramanujan graphs. In our proof of this bound, we also show that the "weak" Meyniel's conjecture holds for expander graph families of bounded degree.

Institution

Affiliation not imported yet

This author record came from a source that does not expose affiliation metadata. Once the author claims the profile or we enrich the record from another provider, this section will link to the concrete institution.

Topic footprint