Sparse regular induced subgraphs in \(2P_3\)-free graphs
type: Item
instance of: scholarly article
title: Sparse regular induced subgraphs in \(2P_3\)-free graphs
zbMATH Open document ID: 1506.05201
author: Vadim Lozin
author: Raffaele Mosca
author: Christopher Purcell
published in: Discrete Optimization
publication date: 2018-10-18T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6958403
zbMATH Keywords: regular graph
zbMATH Keywords: induced subgraph
zbMATH Keywords: polynomial-time algorithm
MaRDI profile type: Publication
full work available at URL: j.disopt.2013.08.001
OpenAlex ID: W1982810881
cites work: Maximum \(k\)-regular induced subgraphs
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: TWO THEOREMS IN GRAPH THEORY
cites work: 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
cites work: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
cites work: Independent sets in extensions of 2\(K_{2}\)-free graphs
cites work: Maximum regular induced subgraphs in \(2P_3\)-free graphs
cites work: Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
cites work: On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
cites work: Satgraphs and independent domination. I
cites work: The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
cites work: Large \(2P_ 3\)-free graphs with bounded degree
DOI: 10.1016/J.DISOPT.2013.08.001
description: scientific article; zbMATH DE number 6958403