Independent Sets in Classes Related to Chair-Free Graphs

DOI10.1007/978-3-319-29221-2_19MaRDI QIDQ2795949zbMATH OpenOpenAlexFDO

Authors T. Karthick

Publication date 23 March 2016

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.02011

zbMATH Keywords

chair-free graphsclaw-free graphsclique separatorsgraph algorithmsindependent setsmodular decomposition

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. MWIS is known to be $NP$-complete in general, even under various restrictions. Let $S_{i,j,k}$ be the graph consisting of three induced paths of lengths $i,j,k$ with a common initial vertex. The complexity of the MWIS problem for $S_{1,2,2}$-free graphs, and for $S_{1,1,3}$-free graphs are open. In this paper, we show that the MWIS problem can solved in polynomial time for ($S_{1,2,2}$, $S_{1,1,3}$, co-chair)-free graphs, by analyzing the structure of the subclasses of this class of graphs. This extends some known results in the literature.

Recommendations

• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• Independent \([1,k]\)-sets in graphs
• Independent sets in k-chromatic graphs
• Independent sets in graphs
• Independent sets and partitions of graphs
• scientific article; zbMATH DE number 5593359
• Independent sets of m,n-gonal graphs
• On independent position sets in graphs
• Independent sets in hypergraphs
• scientific article; zbMATH DE number 31760

Cites work

• A Linear Recognition Algorithm for Cographs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Decomposition by clique separators
• Graph Classes: A Survey
• Graphs without large apples and the maximum weight independent set problem
• scientific article; zbMATH DE number 5761816 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Independent sets of maximum weight in apple-free graphs
• Maximum independent sets in graphs of low degree
• Maximum weight independent sets in (P₆, co-banner)-free graphs
• Maximum weight independent sets in classes related to claw-free graphs
• Maximum weight independent sets in hole- and dart-free graphs
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• Modular decomposition and transitive orientation
• New sufficient conditions for \(\alpha\)-redundant vertices
• On (\(P_{5}\), diamond)-free graphs
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• On diameters and radii of bridged graphs
• On finding augmenting graphs
• On maximal independent sets of vertices in claw-free graphs
• On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• Some results on graphs without long induced paths
• Stable sets in certain \(P_6\)-free graphs
• Stable sets in two subclasses of banner-free graphs
• The complexity of generalized clique packing
• The ellipsoid method and its consequences in combinatorial optimization
• The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
• Weighted independent sets in a subclass of P₆-free graphs
• Weighted independent sets in classes of \(P_6\)-free graphs

Cited in

(8)

• Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes
• Maximum weight independent sets for (\(S_{1,2,4}\), triangle)-free graphs in polynomial time
• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• On independent sets in the class graph of a finite group.
• Weighted independent sets in classes of \(P_6\)-free graphs
• Maximum weight independent sets in classes related to claw-free graphs
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Maximum weight independent sets in hole- and co-chair-free graphs

This page was built for publication: Independent Sets in Classes Related to Chair-Free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2795949)