Characterising graphs with no subdivision of a wheel of bounded diameter

DOI10.1016/J.JCTB.2023.01.004MaRDI QIDQ6038576zbMATH OpenOpenAlexFDO

Authors Johannes Carmesin

Publication date 2 May 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

characterisation of graph classesduality theoremgraph decompositionsgraph minorlocal separatorsshallow minors

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph minors (05C83)

Abstract: We prove that a graph has an r-bounded subdivision of a wheel if and only if it does not have a graph-decomposition of locality r and width at most two.

Recommendations

• Extremal graphs without a semi-topological wheel
• scientific article; zbMATH DE number 5545473
• The spectral radius of graphs with no odd wheels
• Graphs with no 7-wheel subdivision
• Graphs with no induced wheel and no induced antiwheel
• Structure and recognition of graphs with no 6-wheel subdivision
• On r-connected graphs with no semi-topological r-wheel
• On the connected partition dimension of a wheel related graph
• The maximum spectral radius of wheel-free graphs
• scientific article; zbMATH DE number 3884217

Cites work

• A characterization of partial 3-trees
• A minimal condition implying a special K₄-subdivision in a graph
• First-order interpretations of bounded expansion classes
• Forbidden minors characterization of partial 3-trees
• Graph minors. V. Excluding a planar graph
• Grid minors in damaged grids
• Highly connected sets and the excluded grid theorem
• scientific article; zbMATH DE number 1003278 (Why is no real title available?)
• scientific article; zbMATH DE number 7204413 (Why is no real title available?)
• Local 2-separators
• Obstruction set isolation for the gate matrix layout problem
• Sparsity. Graphs, structures, and algorithms
• Towards a splitter theorem for internally 4-connected binary matroids
• Towards tight(er) bounds for the excluded grid theorem
• Unique Colorability and Clique Minors

Cited in

(2)

• Structure and recognition of graphs with no 6-wheel subdivision
• Minimum strong diameter of the strong product of complete multipartite graph and path

This page was built for publication: Characterising graphs with no subdivision of a wheel of bounded diameter

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