Graphs with no induced wheel or antiwheel
classification
🧮 math.CO
cs.DM
keywords
wheelantiwheelcyclegraphsinducedleastchordlessconsequently
read the original abstract
A wheel is a graph that consists of a chordless cycle of length at least 4 plus a vertex with at least three neighbors on the cycle. It was shown recently that detecting induced wheels is an NP-complete problem. In contrast, it is shown here that graphs that contain no wheel and no antiwheel have a very simple structure and consequently can be recognized in polynomial time.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.