10 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 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…
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…
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…
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…