Notes on Graph Product Structure Theory
arXiv:2001.08860 · doi:10.1007/978-3-030-62497-2_32
Abstract
It was recently proved that every planar graph is a subgraph of the strong product of a path and a graph with bounded treewidth. This paper surveys generalisations of this result for graphs on surfaces, minor-closed classes, various non-minor-closed classes, and graph classes with polynomial growth. We then explore how graph product structure might be applicable to more broadly defined graph classes. In particular, we characterise when a graph class defined by a cartesian or strong product has bounded or polynomial expansion. We then explore graph product structure theorems for various geometrically defined graph classes, and present several open problems.
arXiv comment19 pages, 0 figures
References in corpus (9)
- Characterisations and Examples of Graph Classes with Bounded Expansion
- Planar graphs have bounded queue-number
- On Tree-Partition-Width
- Clustered 3-Colouring Graphs of Bounded Degree
- Clique Minors in Cartesian Products of Graphs
- Polynomial expansion and sublinear separators
- Minor-closed graph classes with bounded layered pathwidth
- List-coloring apex-minor-free graphs
- Two lower bounds for -centered colorings