# On maximal independent sets of vertices in claw-free graphs

@article{Minty1980OnMI, title={On maximal independent sets of vertices in claw-free graphs}, author={George J. Minty}, journal={J. Comb. Theory, Ser. B}, year={1980}, volume={28}, pages={284-304} }

Abstract A graph is claw-free if: whenever three (distinct) vertices are joined to a single vertex, those three vertices are a nonindependent (nonstable) set. Given a finite claw-free graph with real numbers (weights) assigned to the vertices, we exhibit an algorithm for producing an independent set of vertices of maximum total weight. This algorithm is “efficient” in the sense of J. Edmonds, that is to say, the number of computational steps required is of polynomial (not exponential or… Expand

#### 451 Citations

On Independent Vertex Sets in Subclasses of Apple-Free Graphs

- Mathematics, Computer Science
- Algorithmica
- 2008

Partial results are obtained on some subclasses of apple-free graphs where the results show that the Maximum Weight Independent Set problem is solvable in polynomial time. Expand

Independence and Efficient Domination on P6-free Graphs

- Mathematics, Computer Science
- SODA
- 2016

This work gives an nO(log2 n) time algorithm for the Maximum Weight Independent Set problem on graphs excluding the path P6 on 6 vertices as an induced subgraph and gives a polynomial-time algorithm for Maximum Weight Efficient Dominating Set on P6-free graphs. Expand

Dominating set is fixed parameter tractable in claw-free graphs

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2011

It is shown that for any t@?N, the Clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs, and the arguments imply that the related Connected Dominating Set and Dominating Clique problems are W[2]-hard in these graph classes. Expand

Using Bounded Degree Spanning Trees in the Design of Efficient Algorithms on Claw-Free Graphs

- Mathematics, Computer Science
- WADS
- 1989

This work shows how to compute efficiently in parallel a binary tree that will be a rooted spanning tree of the claw-free graph and solves problems on claw- free graphs by a divide-and-conquer strategy. Expand

icient Domination on P 6-free Graphs

- 2017

In the Maximum Weight Independent Set problem, the input is a graph G , every vertex has a non-negative integer weight, and the task is to nd a set S of pairwise non-adjacent vertices, maximizing… Expand

On weights of induced paths and cycles in claw-free and K 1 ,r -free graphs

- Mathematics
- 2001

Let G be a K1,r -free graph (r ≥ 3) on n vertices. We prove that, for any induced path or induced cycle on k vertices in G (k ≥ 2r - 1 or k ≥ 2r, respectively), the degree sum of its vertices is at… Expand

Sequential Elimination Graphs ⋆

- 2009

A graph is chordal if it does not contain any induced cycle of size greater than three. An alternative characterization of chordal graphs is via a perfect elimination ordering, which is an ordering… Expand

The structure of claw-free graphs

- Mathematics, Computer Science
- Surveys in Combinatorics
- 2005

It is shown that every connected claw-free graph can be obtained from one of the basic claw- free graphs by simple expansion operations. Expand

Weighted independent sets in a subclass of P6-free graphs

- Mathematics, Computer Science
- Discret. Math.
- 2016

It is shown that the MWIS problem can be solved in time $O(n^3m)$ for ($P_6), banner-free graphs by analyzing the structure of subclasses of these class of graphs. Expand

Elimination Graphs

- Mathematics, Computer Science
- ICALP
- 2009

An extension of chordal graphs whereby the neighbors of v that occur later than v in the elimination order have at most k independent vertices is defined, and several natural classes of graphs are sequentially k -independent for small k . Expand

#### References

SHOWING 1-10 OF 13 REFERENCES

TWO THEOREMS IN GRAPH THEORY.

- Computer Science, Medicine
- Proceedings of the National Academy of Sciences of the United States of America
- 1957

Two theorems are states: Theorem 1 gives a necessary and sufficient condition for recognizing whether a matching is maximum and provides an algorithm for Problem 3, while Theorem 2 yields an algorithms for Problems 1 and 2. Expand

Maximum matching and a polyhedron with 0,1-vertices

- Computer Science
- 1965

The emphasis in this paper is on relating the matching problem to the theory of continuous linear programming, and the algorithm described does not involve any "blind-alley programming" -which, essentially, amounts to testing a great many combinations. Expand

A CHARACTERIZATION OF COMPARABILITY GRAPHS AND OF INTERVAL GRAPHS

- Mathematics
- 1964

Let P . Let G ( P , P , and whose edges ( a , b ) connect vertices for which either a b or b a . A graph G with vertices P for which there exists a partial ordering G = G ( P , In §2 we state and… Expand

The interchange graph of a finite graph

- Mathematics
- 1965

Let G be a finite graph. The interchange graph G' of G, has a vertex corresponding to each edge of G, two vertices of G' being connected if the corresponding edges of G have a common vertex in G. In… Expand

Paths, Trees, and Flowers

- Mathematics
- 1965

A graph G for purposes here is a finite set of elements called vertices and a finite set of elements called edges such that each edge meets exactly two vertices, called the end-points of the edge. An… Expand

Strongly regular graphs, partial geometries and partially balanced designs.

- Mathematics
- 1963

This paper introduced the concept of a partial geometry, which serves to unify and generalize certain theorems on embedding of nets, and uniqueness of association schemes of partially balanced… Expand

Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile

- Computer Science, Mathematics
- Discret. Math.
- 1980

Cette procedure est differente de celle de Minty laquelle commence par chercher s'il existe des chaines augmentantes de longueur trois ou cinq et ce par enumeration, and ensuite a construire pour chaque couple of sommets insatures non voisins, un graphe annexe and a y appliquer l'algorithme du couplage d'Edmonds afin of detecter l'. Expand

T

- L. SAATY, “Finite Graphs and Networks,” McGraw-Hill, New York,
- 1965