From the 1 of 12 linked papers with an AI index.
12 papers
Optimal tree-decompositions with bags of bounded pathwidth
Kevin Hendrey, Robert Hickingbotham, JÄdrzej Hodor +1
The paper proves that every planar graph admits an optimal-width tree‑decomposition whose bags induce subgraphs of pathwidth at most three, and extends similar bounded‑pathwidth ba…
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…
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…
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 …
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…