2015/02/26 by Frédéric Maffray, Maffray, Frédéric
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1502.07484
arxiv created 2015/02/26 · arxiv updated 2015/02/27
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.