Detecting wheels

Abstract

A \emph{wheel} is a graph made of a cycle of length at least~4 together with a vertex that has at least three neighbors in the cycle. We prove that the problem whose instance is a graph $G$ and whose question is "does $G$ contains a wheel as an induced subgraph" is NP-complete. We also settle the complexity of several similar problems.

References in corpus (1)

• Algorithms for perfectly contractile graphs

Cited by in corpus (2)

• The (theta, wheel)-free graphs Part I: only-prism and only-pyramid graphs
• Wheel-free planar graphs