18 citations · 62 across the 29 of their papers we have counts for
8 papers · 1 filter
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…
Odd colourings, conflict-free colourings and strong colouring numbers
Robert Hickingbotham
The odd chromatic number and the conflict-free chromatic number are new graph parameters introduced by Petruševski and Škrekovski [2021] and Fabrici, Lužar, Rindošová and Soták [20…
The product structure of squaregraphs
Robert Hickingbotham, Paul Jungeblut, Laura Merker +1
A squaregraph is a plane graph in which each internal face is a -cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to…
Three-dimensional graph products with unbounded stack-number
David Eppstein, Robert Hickingbotham, Laura Merker +3
We prove that the stack-number of the strong product of three -vertex paths is . The best previously known upper bound was . No non-trivial lower bound was kno…