13 papers
Countable Graphs with Finite Path-width: Characterisation and Universality
Tony Huynh, Freddie Illingworth, Nikolai Karol +4
We study path-width and the closely related parameter line-width in countably infinite graphs. Our first result characterises the graphs of finite path-width: they are the graphs t…
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…
The Dominating 4-Colour Theorem
António Girão, Freddie Illingworth, Bojan Mohar +6
A "dominating -model" in a graph is a sequence of pairwise vertex-disjoint connected subgraphs of , such that whenever every vertex…
Optimal Tree-Decompositions with Bags of Bounded Treewidth
Kevin Hendrey, David R. Wood
We prove that several natural graph classes have tree-decompositions with minimum width such that each bag has bounded treewidth. For example, every planar graph has a tree-decompo…
Embedding Graphs of Simple Treewidth into Sparse Products
Kevin Hendrey, David R. Wood, Jung Hon Yip
We study embeddings of graphs with bounded treewidth or bounded simple treewidth into the undirected graph underlying the directed product of two directed graphs. If the factors ha…
On universal graphs for trees and treewidth graphs
Neel Kaul, David R. Wood
Let be the minimum number of edges in a graph that contains every -vertex tree as a subgraph. Chung and Graham [J. London Math. Soc. 1983] claim to prove that $s(n)\leqsl…
Structure of -Matching-Planar Graphs
Kevin Hendrey, Nikolai Karol, David R. Wood
For , we define a simple topological graph (that is, a graph drawn in the plane such that every pair of edges intersect at most once, including endpoints) to be…
Polynomial Bounds in the Apex Minor Theorem
Kevin Hendrey, David R. Wood
A graph is "apex" if is planar for some vertex . Eppstein [Algorithmica, 2000] showed that for a minor-closed class , the graphs in …
Short Paths in the Planar Graph Product Structure Theorem
Kevin Hendrey, David R. Wood
The Planar Graph Product Structure Theorem of Dujmović et al. [J. ACM '20] says that every planar graph is contained in for some planar graph wi…
Treewidth 2 in the Planar Graph Product Structure Theorem
Marc Distel, Kevin Hendrey, Nikolai Karol +2
We prove that every planar graph is contained in for some graphs and both with treewidth 2. This resolves a question of Liu, Norin and W…
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…
Clustered Colouring of Graph Products
Rutger Campbell, J. Pascal Gollin, Kevin Hendrey +5
A colouring of a graph has clustering if the maximum number of vertices in a monochromatic component equals . Motivated by recent results showing that many natural graph…
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…