Graphs That Do Not Contain a Cycle with a Node That Has at Least Two Neighbors on It

DOI10.1137/11084933XzbMath1261.05087arXiv1309.1841WikidataQ59902617 ScholiaQ59902617MaRDI QIDQ4915184

Kristina Vušković, Pierre Aboulker, Marko Radovanović, Nicolas Trotignon

Publication date: 9 April 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

connectivityinduced subgraphwheelspropeller

Mathematics Subject Classification ID

Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (11)

Excluding clocks ⋮ Using SPQR-trees to speed up algorithms based on 2-cutset decompositions ⋮ The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs ⋮ Edge-colouring and total-colouring chordless graphs ⋮ Induced subgraphs and tree decompositions V. one neighbor in a hole ⋮ On Triangle-Free Graphs That Do Not Contain a Subdivision of the Complete Graph on Four Vertices as an Induced Subgraph ⋮ Excluding cycles with a fixed number of chords ⋮ Using SPQR-trees to speed up recognition algorithms based on 2-cutsets ⋮ Excluding 4‐Wheels ⋮ Vertex elimination orderings for hereditary graph classes ⋮ Wheel-free planar graphs

Uses Software

• Algorithm 447

This page was built for publication: Graphs That Do Not Contain a Cycle with a Node That Has at Least Two Neighbors on It