Graph product structure for non-minor-closed classes

DOI10.1016/j.jctb.2023.03.004zbMath1519.05211arXiv1907.05168OpenAlexW3014452398MaRDI QIDQ6170788

Pat Morin, Vida Dujmović, David R. Wood

Publication date: 10 August 2023

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

graph powernon-repetitive colouringgraph productnearest neighbour graphqueue layoutframed graphmap graph\(k\)-planar graphcentered colouringshortcut system

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Graph operations (line graphs, products, etc.) (05C76)

Related Items (4)

Twin-width II: small classes ⋮ Sparse universal graphs for planarity ⋮ Shallow Minors, Graph Products, and Beyond-Planar Graphs ⋮ Treewidth, Circle Graphs, and Circular Drawings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Nonrepetitive colouring via entropy compression
• On crossing numbers of geometric proximity graphs
• On two dual classes of planar graphs
• Colouring graphs with bounded generalized colouring number
• A partial k-arboretum of graphs with bounded treewidth
• Characterizing and recognizing 4-map graphs
• Recognizing string graphs is decidable
• Polynomial bounds for centered colorings on proper minor-closed graph classes
• Notes on graph product structure theory
• Nonrepetitive graph colouring
• An improved planar graph product structure theorem
• An annotated bibliography on 1-planarity
• Layered separators in minor-closed graph classes with applications
• Recognizing hole-free 4-map graphs in cubic time
• Graph Theory
• Parameters Tied to Treewidth
• A Separator Theorem for String Graphs and its Applications
• Map graphs
• On Graphs Which Contain All Sparse Graphs
• Crossing-Free Subgraphs
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Implicat Representation of Graphs
• Improper colourings inspired by Hadwiger's conjecture
• Nonrepetitive colorings of graphs
• Adjacency Labelling for Planar Graphs (and Beyond)
• Planar graphs have bounded nonrepetitive chromatic number
• Planar Graphs Have Bounded Queue-Number
• Improved Bounds for Centered Colorings
• PROXIMITY GRAPHS: E, δ, Δ, χ AND ω
• Structure of Graphs with Locally Restricted Crossings
• Applications of a New Separator Theorem for String Graphs
• Clustered 3-colouring graphs of bounded degree
• Proofs from THE BOOK
• Queue layouts of planar 3-trees
• Routing with guaranteed delivery in ad hoc wireless networks
• Improved product structure for graphs on surfaces
• Book embeddings of nonplanar graphs with small faces in few pages

This page was built for publication: Graph product structure for non-minor-closed classes