Product structure extension of the Alon-Seymour-Thomas theorem

DOI10.1137/23M1591773MaRDI QIDQ6573005zbMATH OpenFDO

Authors Vida Dujmović, David Eppstein, Robert Hickingbotham, Gwenaël Joret, Piotr Micek, Pat Morin, Michał T. Seweryn, David R. Wood

Publication date 16 July 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/23M1591773

zbMATH Keywords

graph minorplanar graphproductseparatortreewidth

Mathematics Subject Classification ID

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

Recommendations

• Product structure of graphs with an excluded minor
• Linearity of grid minors in treewidth with applications through bidimensionality
• Tree-width and planar minors
• Product structure of graph classes with bounded treewidth
• Product structure of graph classes with bounded treewidth

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• A separator theorem for graphs of bounded genus
• A Separator Theorem for Nonplanar Graphs
• A Separator Theorem for Planar Graphs
• An improved planar graph product structure theorem
• Applications of a Planar Separator Theorem
• Clustered 3-colouring graphs of bounded degree
• Defective and clustered graph colouring
• Dense graphs have \(K_{3,t}\) minors
• Graph minors. V. Excluding a planar graph
• Graph minors. XVI: Excluding a non-planar graph
• Graph product structure for non-minor-closed classes
• Graphs on surfaces
• scientific article; zbMATH DE number 3970774 (Why is no real title available?)
• scientific article; zbMATH DE number 1944139 (Why is no real title available?)
• Improved product structure for graphs on surfaces
• Layered separators in minor-closed graph classes with applications
• On the excluded minor structure theorem for graphs of large tree-width
• Parameters tied to treewidth
• Planar graphs have bounded queue-number
• Product structure of graph classes with bounded treewidth
• Shallow Minors, Graph Products, and Beyond-Planar Graphs
• The Grid-Minor theorem revisited
• The product structure of squaregraphs
• Treewidth of graphs with balanced separations

Cited in

(5)

• Product structure of graph classes with bounded treewidth
• Product structure of graph classes with bounded treewidth
• Product structure of graphs with an excluded minor
• Product structure of graph classes with strongly sublinear separators
• A product structure for planar graphs

This page was built for publication: Product structure extension of the Alon-Seymour-Thomas theorem

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