On maximal independent sets of vertices in claw-free graphs
From MaRDI portal
Publication:1139605
DOI10.1016/0095-8956(80)90074-XzbMath0434.05043WikidataQ30049355 ScholiaQ30049355MaRDI QIDQ1139605
Publication date: 1980
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
05C35: Extremal problems in graph theory
Related Items
WELL-COVERED GRAPHS: A SURVEY, Polynomial algorithm for finding the largest independent sets in graphs without forks, Unnamed Item, On the Stable Set Polytope of Claw-Free Graphs, Hard graphs for the maximum clique problem, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, A branch and bound algorithm for the maximum clique problem, On a classification of independence systems, On a classification of independence systems, On minimal prime extensions of a four-vertex graph in a prime graph, Augmenting graphs for independent sets, Cycles of given length in some \(K_{1,3}\)-free graphs, Stability in CAN-free graphs, Recent trends in combinatorial optimization, Finding maximum cliques in arbitrary and in special graphs, Penta-extensions of hereditary classes of graphs, On the feedback vertex set polytope of a series-parallel graph, New applications of clique separator decomposition for the maximum weight stable set problem, Clique-circulants and the stable set polytope of fuzzy circular interval graphs, The stable set polytope of quasi-line graphs, On finding augmenting graphs, Gear composition and the stable set polytope, Finding augmenting chains in extensions of claw-free graphs, Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes, Brick decompositions and the matching rank of graphs, The struction of a graph: Application to CN-free graphs, The complexity of generalized clique packing, Quelques utilisations de la STRUCTION. (Some applications of STRUCTION), Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé, 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, The ellipsoid method and its consequences in combinatorial optimization, On stable set polyhedra for K//(1,3)free graphs, Stability number of bull- and chair-free graphs, Stable sets in certain \(P_6\)-free graphs, The maximum clique problem, Extending matchings in graphs: A survey, Extending matchings in claw-free graphs, Edge-disjoint packings of graphs, An exact algorithm for the maximum stable set problem, The structure of well-covered graphs and the complexity of their recognition problems, Claw-free graphs---a survey, Matching extension in \(K_{1,r}\)-free graphs with independent claw centers, A nice class for the vertex packing problem, On the use of Boolean methods for the computation of the stability number, Independent domination in finitely defined classes of graphs, Scalar aggregation in inconsistent databases., On linear and circular structure of (claw, net)-free graphs, Stability number of bull- and chair-free graphs revisited, 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., On the cut polyhedron., Induced matchings in intersection graphs., Stabex method for extension of \(\alpha\)-polynomial hereditary classes., Stability in \(P_5\)- and banner-free graphs, On claw-free asteroidal triple-free graphs, Independent sets in extensions of 2\(K_{2}\)-free graphs, Perfect stables in graphs, Packing triangles in bounded degree graphs., Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time., On the stable set problem in special \(P_{5}\)-free graphs, Independent sets of maximum weight in (\(p,q\))-colorable graphs., Dominating sets and Hamiltonicity in \(K_{1,3}\)-free graphs, On the vertex packing problem, Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs, Classes of perfect graphs, Augmenting chains in graphs without a skew star., Partitioning cographs into cliques and stable sets, Unnamed Item, Squares of Intersection Graphs and Induced Matchings, Star-shape, Radon number, and minty graphs, A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs, Tree-Width and Optimization in Bounded Degree Graphs, The Maximum Independent Set Problem in Planar Graphs, A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles, Determining the number of internal stability of a graph, An algorithm for the maximum internally stable set in a weighted graph, Local transformations of graphs preserving independence number
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
