2012/01/01 by Pierre Aboulker, Marko Radovanović, Nicolas Trotignon +1 · 12 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Analogy #Complexity and Algorithms in Graphs #Decomposition #Induced subgraph #Induced subgraph isomorphism problem #Limits and Structures in Graph Theory #Node (physics) #Polynomial #Time complexity #cs.DM #math.CO #msc:05C75
paper · pdf · doi:10.1137/11084933x
published in SIAM Journal on Discrete Mathematics 26(4), 1510-1531 (Society for Industrial and Applied Mathematics)
openalex publication_date 2012/01/01 · arxiv created 2013/09/07 · arxiv updated 2016/03/27 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
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 and polynomial time algorithms for vertex-coloring and edge-coloring.