Treewidth of grid subsets

DOI10.1007/S00493-017-3538-5MaRDI QIDQ2416442zbMATH OpenOpenAlexWikidataFDO

Authors Eli Berger, Zdeněk Dvoržak, Serguei Norine

Publication date 23 May 2019

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.06441

zbMATH Keywords

tree-widthseparating set3-dimensional grid

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: Let Q_n be the graph of n times n times n cube with all non-decreasing diagonals (including the facial ones) in its constituent unit cubes. Suppose that a subset S of V(Q_n) separates the left side of the cube from the right side. We show that S induces a subgraph of tree-width at least n/sqrt{18}-1. We use a generalization of this claim to prove that the vertex set of Q_n cannot be partitioned to two parts, each of them inducing a subgraph of bounded tree-width.

Recommendations

• On the treewidth of toroidal grids
• scientific article; zbMATH DE number 1696534
• On tree-partition-width
• Highly connected sets and the excluded grid theorem
• Tree-partitions of \(k\)-trees with applications in graph layout.

Cited in

(5)

• Separating layered treewidth and row treewidth
• On generalized choice and coloring numbers
• Colouring strong products
• Losing Treewidth by Separating Subsets
• Boxicity and treewidth

This page was built for publication: Treewidth of grid subsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2416442)