Graphs that do not contain a cycle with a node that has at least two neighbors on it

Abstract

We recall several known results about minimally 2-connected graphs, and show that they all follow from a decomposition theorem. Starting from an analogy with critically 2-connected graphs, we give structural characterizations of the classes of graphs that do not contain as a subgraph and as an induced subgraph, a cycle with a node that has at least two neighbors on the cycle. From these characterizations we get polynomial time recognition algorithms for these classes, as well as polynomial time algorithms for vertex-coloring and edge-coloring.

References in corpus (4)

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Detecting induced subgraphs
• Algorithms for perfectly contractile graphs
• On graphs with no induced subdivision of $K_4$

Cited by in corpus (5)

• Edge-colouring and total-colouring chordless graphs
• The (theta, wheel)-free graphs Part I: only-prism and only-pyramid 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
• Wheel-free planar graphs