Sparse regular induced subgraphs in \(2P_3\)-free graphs

DOI10.1016/j.disopt.2013.08.001zbMath1506.05201OpenAlexW1982810881MaRDI QIDQ1799386

Raffaele Mosca, Christopher Purcell, Vadim V. Lozin

Publication date: 18 October 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2013.08.001

zbMATH Keywords

polynomial-time algorithmregular graphinduced subgraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Induced 2-regular subgraphs in \(k\)-chordal cubic graphs ⋮ A sufficient condition to extend polynomial results for the maximum independent set problem ⋮ New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ Induced cycles in graphs

Cites Work

• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• Maximum regular induced subgraphs in \(2P_3\)-free graphs
• Satgraphs and independent domination. I
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Large \(2P_ 3\)-free graphs with bounded degree
• Maximum \(k\)-regular induced subgraphs
• TWO THEOREMS IN GRAPH THEORY
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Maximum matching and a polyhedron with 0,1-vertices
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: Sparse regular induced subgraphs in \(2P_3\)-free graphs