On maximal independent sets of vertices in claw-free graphs
From MaRDI portal
Publication:1139605
DOI10.1016/0095-8956(80)90074-XzbMath0434.05043DBLPjournals/jct/Minty80WikidataQ30049355 ScholiaQ30049355MaRDI QIDQ1139605
Publication date: 1980
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Related Items (only showing first 100 items - show all)
On claw-free asteroidal triple-free graphs ⋮ Edge-disjoint packings of graphs ⋮ An exact algorithm for the maximum stable set problem ⋮ Quelques utilisations de la STRUCTION. (Some applications of STRUCTION) ⋮ Augmenting approach for some maximum set problems ⋮ Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs ⋮ On the feedback vertex set polytope of a series-parallel graph ⋮ Enumeration of maximal irredundant sets for claw-free graphs ⋮ Finding and counting small induced subgraphs efficiently ⋮ Weighted independent sets in classes of \(P_6\)-free graphs ⋮ On independent vertex sets in subclasses of apple-free graphs ⋮ The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs ⋮ The structure of well-covered graphs and the complexity of their recognition problems ⋮ Well-covered triangulations. IV ⋮ Claw-free graphs---a survey ⋮ Matching extension in \(K_{1,r}\)-free graphs with independent claw centers ⋮ Tent and a subclass of \(P_{5}\)-free graphs ⋮ A nice class for the vertex packing problem ⋮ On the use of Boolean methods for the computation of the stability number ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ A sufficient condition to extend polynomial results for the maximum independent set problem ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ A note on anti-coordination and social interactions ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect ⋮ Colouring squares of claw-free graphs ⋮ On the recognition of fuzzy circular interval graphs ⋮ Independent domination in finitely defined classes of graphs ⋮ Coloring fuzzy circular interval graphs ⋮ Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Scalar aggregation in inconsistent databases. ⋮ On linear and circular structure of (claw, net)-free graphs ⋮ Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time ⋮ Stability number of bull- and chair-free graphs revisited ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ On the facets of the stable set polytope of quasi-line graphs ⋮ An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs ⋮ On easy and hard hereditary classes of graphs with respect to the independent set problem ⋮ On the structure and stability number of \(P_{5}\)- and co-chair-free graphs ⋮ On well-covered triangulations. I ⋮ \(P_{5}\)-free augmenting graphs and the maximum stable set problem ⋮ Stable sets in two subclasses of banner-free graphs ⋮ Some results on maximum stable sets in certain \(P_{5}\)-free graphs ⋮ Clique family inequalities for the stable set polytope of quasi-line graphs. ⋮ Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs ⋮ A polynomial algorithm for the minimum weighted clique cover problem on claw-free perfect graphs ⋮ Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems ⋮ Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ Dominating set is fixed parameter tractable in claw-free graphs ⋮ The ellipsoid method and its consequences in combinatorial optimization ⋮ On stable set polyhedra for K//(1,3)free graphs ⋮ On the cut polyhedron. ⋮ Induced matchings in intersection graphs. ⋮ Stabex method for extension of \(\alpha\)-polynomial hereditary classes. ⋮ Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs ⋮ Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs ⋮ Weighted well-covered claw-free graphs ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Clique-circulants and the stable set polytope of fuzzy circular interval graphs ⋮ The stable set polytope of quasi-line graphs ⋮ An \(\mathcal O(n\sqrt m)\) algorithm for the weighted stable set problem in \{claw, net\}-free graphs with \(\alpha(G)\geq 4\) ⋮ On finding augmenting graphs ⋮ A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs ⋮ On the algorithmic aspects of strong subcoloring ⋮ Correction to: ``A connection between sports and matroids: how many teams can we beat? ⋮ On well-covered pentagonalizations of the plane ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ Stability number of bull- and chair-free graphs ⋮ On well-covered triangulations. II. ⋮ On well-covered triangulations. III ⋮ On minimal prime extensions of a four-vertex graph in a prime graph ⋮ Augmenting graphs for independent sets ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ On packing shortest cycles in graphs ⋮ Gear composition and the stable set polytope ⋮ Finding augmenting chains in extensions of claw-free graphs ⋮ Graphs without large apples and the maximum weight independent set problem ⋮ Cycles of given length in some \(K_{1,3}\)-free graphs ⋮ Stability in CAN-free graphs ⋮ Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes ⋮ A dichotomy in the complexity of consistent query answering for queries with two atoms ⋮ Mind the independence gap ⋮ Grundy dominating sequences on \(X\)-join product ⋮ Some classical combinatorial problems on circulant and claw-free graphs: The isomorphism and coloring problems on circulant graphs and the stable set problem on claw-free graphs ⋮ Stability in \(P_5\)- and banner-free graphs ⋮ Parameterized complexity of independent set in H-free graphs ⋮ Recent trends in combinatorial optimization ⋮ Brick decompositions and the matching rank of graphs ⋮ Stable sets in certain \(P_6\)-free graphs ⋮ Finding maximum cliques in arbitrary and in special graphs ⋮ The struction of a graph: Application to CN-free graphs ⋮ The maximum clique problem ⋮ Penta-extensions of hereditary classes of graphs ⋮ Extending matchings in graphs: A survey ⋮ Extending matchings in claw-free graphs ⋮ The complexity of generalized clique packing
Cites Work
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Strongly regular graphs, partial geometries and partially balanced designs
- On the notion of balance of a signed graph
- TWO THEOREMS IN GRAPH THEORY
- Paths, Trees, and Flowers
- The interchange graph of a finite graph
- Maximum matching and a polyhedron with 0,1-vertices
- A Characterization of Comparability Graphs and of Interval Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On maximal independent sets of vertices in claw-free graphs
