Source author record

Bruce Reed

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms

Catalog footprint

Research overview

12works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

Linear bounds on treewidth in terms of excluded planar minors

One of the fundamental results in graph minor theory is that for every planar graph $H$ , there is a minimum integer $f(H)$ such that graphs with no minor isomorphic to $H$ have treewidth at most $f(H)$ . A lower bound for ${f(H)}$ can be obtained by considering the maximum integer $k$ such that $H$ contains $k$ vertex-disjoint cycles. There exists a graph of treewidth ${Ω(k\log k)}$ which does not contain $k$ vertex-disjoint cycles, from which it follows that ${f(H) = Ω(k\log k)}$ . In particular, if ${f(H)}$ is linear in ${\lvert{V(H)}\rvert}$ for graphs $H$ from a subclass of planar graphs, it is necessary that $n$ -vertex graphs from the class contain at most ${O(n/\log(n))}$ vertex-disjoint cycles. We ask whether this is also a sufficient condition, and demonstrate that this is true for classes of planar graphs with bounded component size. For an $n$ -vertex graph $H$ which is a disjoint union of $r$ cycles, we show that ${f(H) \leq 3n/2 + O(r^2 \log r)}$ , and improve this to ${f(H) \leq n + O(\sqrt{n})}$ when ${r = 2}$ . In particular this bound is linear when ${r=O(\sqrt{n}/\log(n))}$ . We present a linear bound for ${f(H)}$ when $H$ is a subdivision of an $r$ -edge planar graph for any constant $r$ . We also improve the best known bounds for ${f(H)}$ when $H$ is the wheel graph or the ${4 \times 4}$ grid, obtaining a bound of $160$ for the latter.

preprint2022arXiv

Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex I: An Asymptotic Result

In this paper and a companion paper, we prove that, if $m$ is sufficiently large, every graph on $m+1$ vertices that has a universal vertex and minimum degree at least $\lfloor \frac{2m}{3} \rfloor$ contains each tree $T$ with $m$ edges as a subgraph. Our result confirms, for large $m$ , an important special case of a recent conjecture by Havet, Reed, Stein, and Wood. The present paper already contains an approximate version of the result.

preprint2022arXiv

Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex II: A Tight Result

We prove that, if $m$ is sufficiently large, every graph on $m+1$ vertices that has a universal vertex and minimum degree at least $\lfloor \frac{2m}{3} \rfloor$ contains each tree $T$ with $m$ edges as a subgraph. Our result confirms, for large $m$ , an important special case of a conjecture by Havet, Reed, Stein, and Wood. The present paper builds on the results of a companion paper in which we proved the statement for all trees having a vertex that is adjacent to many leaves.

preprint2020arXiv

Cops and robbers on oriented toroidal grids

The game of cops and robbers is a well-known game played on graphs. In this paper we consider the straight-ahead orientations of 4-regular quadrangulations of the torus and the Klein bottle and we prove that their cop number is bounded by a constant. We also show that the cop number of every k-regularly oriented toroidal grid is at most 13.

preprint2020arXiv

Notes on Tree- and Path-chromatic Number

Tree-chromatic number is a chromatic version of treewidth, where the cost of a bag in a tree-decomposition is measured by its chromatic number rather than its size. Path-chromatic number is defined analogously. These parameters were introduced by Seymour (JCTB 2016). In this paper, we survey all the known results on tree- and path-chromatic number and then present some new results and conjectures. In particular, we propose a version of Hadwiger's Conjecture for tree-chromatic number. As evidence that our conjecture may be more tractable than Hadwiger's Conjecture, we give a short proof that every $K_5$ -minor-free graph has tree-chromatic number at most $4$ , which avoids the Four Colour Theorem. We also present some hardness results and conjectures for computing tree- and path-chromatic number.

preprint2016arXiv

Acyclic edge colourings of graphs with large girth

An edge colouring of a graph $G$ is called acyclic if it is proper and every cycle contains at least three colours. We show that for every $\varepsilon>0$ , there exists a $g=g(\varepsilon)$ such that if $G$ has girth at least $g$ then $G$ admits an acyclic edge colouring with at most $(1+\varepsilon)Δ$ colours.

preprint2015arXiv

Connectivity Preserving Iterative Compaction and Finding 2 Disjoint Rooted Paths in Linear Time

In this paper we show how to combine two algorithmic techniques to obtain linear time algorithms for various optimization problems on graphs, and present a subroutine which will be useful in doing so. The first technique is iterative shrinking. In the first phase of an iterative shrinking algorithm, we construct a sequence of graphs of decreasing size $G_1,\ldots,G_\ell$ where $G_1$ is the initial input, $G_\ell$ is a graph on which the problem is easy, and $G_i$ is obtained from $G_{i+1}$ via some shrinking algorithm. In the second phase we work through the sequence in reverse, repeatedly constructing a solution for a graph from the solution for its successor. In an iterative compaction algorithm, we insist that the graphs decrease by a constant fraction of the entire graph. Another approach to solving optimization problems is to exploit the structural properties implied by the connectivity of the input graph. This approach can be used on graphs which are not highly connected by decomposing an input graph into its highly connected pieces, solving subproblems on these specially structured pieces and then combining their solutions. We combine these two techniques by developing compaction algorithms which when applied to the highly connected pieces preserve their connectivity properties. The structural properties this connectivity implies can be helpful both in finding further compactions in later iterations and when we are manipulating solutions in the second phase of an iterative compaction algorithm. To illustrate how this compaction algorithm can be used as a subroutine, we present a linear time algorithm that given four vertices $\{s_1,s_2,t_1,t_2\}$ of a graph $G$ , either finds a pair of disjoint paths $P_1$ and $P_2$ of $G$ such that $P_i$ has endpoints $s_i$ and $t_i$ , or returns a planar embedding of an auxiliary graph which shows that no such pair exists.

preprint2014arXiv

A Density Version of the Corradi-Hajnal Theorem

For every positive integer $k$ , we show that every graph of order $n$ at least $3k$ with more than $\max\{{2k-1\choose 2}+(2k-1)(n-(2k-1)),{3k-1\choose 2}+(n-(3k-1))\}$ edges has $k$ vertex disjoint cycles, which is a best possible density version of a theorem of Corrádi and Hajnal.

preprint2013arXiv

A linear-time algorithm for finding a complete graph minor in a dense graph

Let g(t) be the minimum number such that every graph G with average degree d(G) \geq g(t) contains a K_{t}-minor. Such a function is known to exist, as originally shown by Mader. Kostochka and Thomason independently proved that g(t) \in Θ(t*sqrt{log t}). This article shows that for all fixed ε> 0 and fixed sufficiently large t \geq t(ε), if d(G) \geq (2+ε)g(t) then we can find this K_{t}-minor in linear time. This improves a previous result by Reed and Wood who gave a linear-time algorithm when d(G) \geq 2^{t-2}.

preprint2011arXiv

Asymptotics of the chromatic number for quasi-line graphs

As proved by Kahn, the chromatic number and fractional chromatic number of a line graph agree asymptotically. That is, for any line graph $G$ we have $χ(G) \leq (1+o(1))χ_f(G)$ . We extend this result to quasi-line graphs, an important subclass of claw-free graphs. Furthermore we prove that we can construct a colouring that achieves this bound in polynomial time, giving us an asymptotic approximation algorithm for the chromatic number of quasi-line graphs.

preprint2011arXiv

Connectivity for bridge-addable monotone graph classes

A class A of labelled graphs is bridge-addable if for all graphs G in A and all vertices u and v in distinct connected components of G, the graph obtained by adding an edge between u and u is also in A; the class A is monotone if for all G in A and all subgraphs H of G, H is also in A. We show that for any bridge-addable, monotone class A whose elements have vertex set 1,...,n, the probability that a uniformly random element of A is connected is at least (1-o_n(1)) e^{-1/2}, where o_n(1) tends to zero as n tends to infinity. This establishes the special case of a conjecture of McDiarmid, Steger and Welsh when the condition of monotonicity is added. This result has also been obtained independently by Kang and Panagiotiou (2011).

preprint2011arXiv

Covering the edges of a random graph by cliques

The clique cover number of a graph G is the minimum number of cliques required to cover the edges of graph G. In this paper we consider the random graph G(n,p), for p constant. We prove that with probability 1-o(1), the clique number of G(n,p) is Theta(n^2/\log^2n).

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.

Bruce Reed

Research overview

Is this your work?

12 publications

Linear bounds on treewidth in terms of excluded planar minors

Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex I: An Asymptotic Result

Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex II: A Tight Result

Cops and robbers on oriented toroidal grids

Notes on Tree- and Path-chromatic Number

Acyclic edge colourings of graphs with large girth

Connectivity Preserving Iterative Compaction and Finding 2 Disjoint Rooted Paths in Linear Time

A Density Version of the Corradi-Hajnal Theorem

A linear-time algorithm for finding a complete graph minor in a dense graph

Asymptotics of the chromatic number for quasi-line graphs

Connectivity for bridge-addable monotone graph classes

Covering the edges of a random graph by cliques

See the researcher in context

Building this map preview