Detecting wheels

DOI10.2298/AADM131128023DMaRDI QIDQ2815233zbMATH OpenFDO

Authors Emilie Diot, Sébastien Tavenas, Nicolas Trotignon

Publication date 27 June 2016

Published in Applicable Analysis and Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.6433

zbMATH Keywords

detectionTruemper configurationswheel

Mathematics Subject Classification ID

Perfect graphs (05C17) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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.

Recommendations

• scientific article; zbMATH DE number 554179
• Identification of the running-state of railway wheelsets
• Wheels and whirls
• A REAPPEARANCE OF WHEELS
• The chromaticity of wheels
• Roads and Wheels
• scientific article; zbMATH DE number 1944643

Cited in

(11)

• The subgraph homeomorphism problem for small wheels
• An efficient algorithm for solving spoked wheels
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• Wheel-free planar graphs
• Graphs with no 7-wheel subdivision
• Wheel-Free Deletion Is W[2]-Hard
• The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
• Graphs with no induced wheel and no induced antiwheel
• Excluding 4-wheels
• Induced minor models. I: Structural properties and algorithmic consequences
• Detecting \(K_{2,3}\) as an induced minor

This page was built for publication: Detecting wheels

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2815233)