Graphs with no 7-wheel subdivision

Abstract

The subgraph homeomorphism problem, SHP($H$), has been shown to be polynomial-time solvable for any fixed pattern graph $H$, but practical algorithms have been developed only for a few specific pattern graphs. Among these are the wheels with four, five, and six spokes. This paper examines the subgraph homeomorphism problem where the pattern graph is a wheel with seven spokes, and gives a result that describes graphs with no $W_7$-subdivision, showing how they can be built up, using certain operations, from smaller `pieces' that meet certain conditions. We also discuss algorithmic aspects of the problem.

97 pages, 47 figures

References in corpus (1)

• Search strategies for developing characterizations of graphs without small wheel subdivisions

Cited by in corpus (3)

• The Structure of $W_4$-Immersion-Free Graphs
• Search strategies for developing characterizations of graphs without small wheel subdivisions
• Topological containment of the 5-clique minus an edge in 4-connected graphs