Sparse regular induced subgraphs in \(2P_3\)-free graphs
From MaRDI portal
Publication:1799386
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
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
