Characterising graphs with no subdivision of a wheel of bounded diameter

2020/08/07 by Johannes Carmesin, Carmesin, Johannes
Computer Science · Engineering · Mathematics · #05C40 #05C75 #05C83 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #graph theory and CDMA systems #math.CO #msc:05C40 #msc:05C75 #msc:05C83

paper · pdf · doi:10.48550/arxiv.2008.03031

arxiv created 2020/08/07 · openalex publication_date 2020/08/07 · arxiv updated 2020/08/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• Graphs with no induced wheel or antiwheel
• A decomposition theorem for ISK4,wheel-free trigraphs
• On wheel-free graphs
• Search strategies for developing characterizations of graphs without small wheel subdivisions
• Excluding 4-wheels