The product structure of squaregraphs

DOI10.1002/JGT.23008MaRDI QIDQ6143380zbMATH OpenFDO

Authors Robert Hickingbotham, Paul Jungeblut, Laura Merker, David R. Wood

Publication date 24 January 2024

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

planar graphproduct structuresquaregraphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A squaregraph is a plane graph in which each internal face is a $4$-cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to a subgraph of the semi-strong product of an outerplanar graph and a path. We generalise this result for infinite squaregraphs, and show that this is best possible in the sense that "outerplanar graph" cannot be replaced by "forest".

Recommendations

• Combinatorics and geometry of finite and infinite squaregraphs
• Notes on graph product structure theory
• scientific article; zbMATH DE number 1545700
• scientific article; zbMATH DE number 4170928

Cites work

• Adjacency Labelling for Planar Graphs (and Beyond)
• An improved planar graph product structure theorem
• Clustered 3-colouring graphs of bounded degree
• Combinatorics and geometry of finite and infinite squaregraphs
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• Improved bounds for centered colorings
• Improved product structure for graphs on surfaces
• Induced subgraphs of product graphs and a generalization of Huang's theorem
• Metric graph theory and geometry: a survey
• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of graphs of bounded tree-width
• Nonrepetitive graph colouring
• On the Genus of Strong Tensor Products of Graphs
• Parameters tied to treewidth
• Planar graphs have bounded nonrepetitive chromatic number
• Planar graphs have bounded queue-number
• Separating layered treewidth and row treewidth
• Shorter Labeling Schemes for Planar Graphs
• Track layouts, layered path decompositions, and leveled planarity

Cited in

(5)

• Product structure extension of the Alon-Seymour-Thomas theorem
• Bounded-degree planar graphs do not have bounded-degree product structure
• Product structure of graphs with an excluded minor
• Structural properties of graph products
• A product structure for planar graphs

This page was built for publication: The product structure of squaregraphs

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