18 citations · 62 across the 29 of their papers we have counts for
32 papers
Asymptotic dimension of graphs excluding an induced or fat minor
Robert Hickingbotham, Freddie Illingworth, Piotr Micek +1
Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). A major open problem in coarse graph theory asks whether, for every fixed gra…
Induced Forest Minor Theorem for Graphs Without an Induced Star
Robert Hickingbotham, Gwenaël Joret
Motivated by recent work on tree independence number, we study the path independence number of a graph : the minimum integer such that there is a path decomposition of w…
Optimal tree-decompositions with bags of bounded pathwidth
Kevin Hendrey, Robert Hickingbotham, Jędrzej Hodor +1
We show that every planar graph has a tree-decomposition with optimal width such that the subgraph induced by each bag has pathwidth at most 3. This bound is best possible, and for…
An Induced -Path Theorem
Robert Hickingbotham, Gwenaël Joret
Given a graph and , a classical theorem of Gallai (1964) states that for every positive integer , the graph contains pairwise vertex-disjo…
Excluding a Forest Induced Minor
Édouard Bonnet, Benjamin Duhamel, Robert Hickingbotham
In the first paper of the Graph Minors series [JCTB '83], Robertson and Seymour proved the Forest Minor theorem: the -minor-free graphs have bounded pathwidth if and only if …
Induced Minors, Asymptotic Dimension, and Baker's Technique
Robert Hickingbotham
Asymptotic dimension is a large-scale invariant of metric spaces that was introduced by Gromov (1993). We prove that every hereditary class of bounded-degree graphs that excludes s…
Binary matroids and degree-boundedness for pivot-minors
Rutger Campbell, James Davies, Robert Hickingbotham
We prove that for every bipartite graph and positive integer , the class of -subgraph-free graphs excluding as a pivot-minor has bounded average degree. Our pro…
Coarse Balanced Separators and Tree-Decompositions
Maria Chudnovsky, Robert Hickingbotham
A classical result of Robertson and Seymour (1986) states that the treewidth of a graph is linearly tied to its separation number: the smallest integer such that, for every wei…
Induced Minors and Region Intersection Graphs
Édouard Bonnet, Robert Hickingbotham
We show that for any positive integers and , there is a -induced-minor-free graph of girth at least that is not a region intersection graph over the class o…
Quasi-isometries between graphs with variable edge lengths
James Davies, Meike Hatzel, Robert Hickingbotham
This paper investigates quasi-isometries between graphs with variable edge lengths. A quasi-isometry is a mapping between metric spaces that approximately preserves distances, allo…
Graphs that are quasi-isometric to graphs with bounded treewidth
Robert Hickingbotham
In this paper, we characterise graphs that are quasi-isometric to graphs with bounded treewidth. Specifically, we prove that a graph is quasi-isometric to a graph with bounded tree…
Treewidth, Hadwiger Number, and Induced Minors
Rutger Campbell, James Davies, Marc Distel +7
Treewidth and Hadwiger number are two of the most important parameters in structural graph theory. This paper studies graph classes in which large treewidth implies the existence o…
Fat minors cannot be thinned (by quasi-isometries)
James Davies, Robert Hickingbotham, Freddie Illingworth +1
We disprove the conjecture of Georgakopoulos and Papasoglu that a length space (or graph) with no -fat minor is quasi-isometric to a graph with no minor. Our counterexam…
Defective and Clustered Colouring of Graphs with Given Girth
Marcin Briański, Robert Hickingbotham, David R. Wood
The defective chromatic number of a graph class is the minimum integer such that for some integer , every graph in is -colourable such that ea…
Cop-width, flip-width and strong colouring numbers
Robert Hickingbotham
Cop-width and flip-width are new families of graph parameters introduced by Toruńczyk (2023) that generalise treewidth, degeneracy, generalised colouring numbers, clique-width and…
Clustered Colouring of Odd--Minor-Free Graphs
Robert Hickingbotham, Dong Yeap Kang, Sang-il Oum +2
The clustered chromatic number of a graph class is the minimum integer such that every graph has a -colouring where each monochromatic compon…
Powers of planar graphs, product structure, and blocking partitions
Marc Distel, Robert Hickingbotham, Michał T. Seweryn +1
We prove that the -power of any planar graph is contained in for some graph with bounded treewidth, some path , and some functio…
The grid-minor theorem revisited
Vida Dujmović, Robert Hickingbotham, Jędrzej Hodor +6
We prove that for every planar graph of treedepth , there exists a positive integer such that for every -minor-free graph , there exists a graph of treewidth a…
The Excluded Tree Minor Theorem Revisited
Vida Dujmović, Robert Hickingbotham, Gwenaël Joret +3
We prove that for every tree of radius , there is an integer such that every -minor-free graph is contained in for some graph with pathwidth at m…
Treewidth, Circle Graphs and Circular Drawings
Robert Hickingbotham, Freddie Illingworth, Bojan Mohar +1
A circle graph is an intersection graph of a set of chords of a circle. We describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples…
Product structure extension of the Alon--Seymour--Thomas theorem
Marc Distel, Vida Dujmović, David Eppstein +6
Alon, Seymour and Thomas [1990] proved that every -vertex graph excluding as a minor has treewidth less than . Illingworth, Scott and Wood [2022] recently…
Graphs of Linear Growth have Bounded Treewidth
Rutger Campbell, Marc Distel, J. Pascal Gollin +5
A graph class has linear growth if, for each graph and every positive integer , every subgraph of with radius at most contains v…
Product structure of graph classes with bounded treewidth
Rutger Campbell, Katie Clinch, Marc Distel +8
We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end…
Induced subgraphs and path decompositions
Robert Hickingbotham
A graph is an induced subgraph of a graph if a graph isomorphic to can be obtained from by deleting vertices. Recently, there has been significant interest in under…