Independent Sets in Classes Related to Chair-Free Graphs
DOI10.1007/978-3-319-29221-2_19zbMath1444.05108arXiv1603.02011OpenAlexW2296360867MaRDI QIDQ2795949
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
graph algorithmsindependent setsmodular decompositionclaw-free graphsclique separatorschair-free graphs
Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Weighted independent sets in classes of \(P_6\)-free graphs
- The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
- Maximum weight independent sets in classes related to claw-free graphs
- On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
- Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
- Maximum weight independent sets in odd-hole-free graphs without dart or without bull
- Maximum weight independent sets in hole- and dart-free graphs
- Graphs without large apples and the maximum weight independent set problem
- Weighted independent sets in a subclass of \(P_6\)-free graphs
- On finding augmenting graphs
- Some results on graphs without long induced paths
- Decomposition by clique separators
- The complexity of generalized clique packing
- On diameters and radii of bridged 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é
- The ellipsoid method and its consequences in combinatorial optimization
- Modular decomposition and transitive orientation
- Stable sets in certain \(P_6\)-free graphs
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- Stable sets in two subclasses of banner-free graphs
- On (\(P_{5}\), diamond)-free graphs
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
- New sufficient conditions for \(\alpha\)-redundant vertices
- On the Maximum Independent Set Problem in Subclasses of Subcubic Graphs
- A Linear Recognition Algorithm for Cographs
- Graph Classes: A Survey
- Independent Sets of Maximum Weight in Apple-Free Graphs
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
This page was built for publication: Independent Sets in Classes Related to Chair-Free Graphs