pith. sign in

arxiv: 1309.1841 · v1 · pith:76CTK7LBnew · submitted 2013-09-07 · 💻 cs.DM · math.CO

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

classification 💻 cs.DM math.CO
keywords graphscyclealgorithmscharacterizationsclassesconnectedcontainleast
0
0 comments X
read the original 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.

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.