Name
Abstract | ||
|---|---|---|
A graph G is claw-free if no induced subgraph of it is isomorphic to the complete bipartite graph K-1,K-3, and it is prime if vertical bar V (G)vertical bar >= 4 and there is no X subset of V (G) with 1 < vertical bar X vertical bar < vertical bar V (G)vertical bar such that every vertex of V(G) \ X with a neighbor in X is adjacent to every vertex of X. In particular, if G is prime, then both G and G(c) are connected. This paper has two main results. The first one is that if G is a prime graph that is not a member of a particular family of exceptions, and H is a prime induced subgraph of G, then ( up to isomorphism) G can be grown from H, adding one vertex at a time, in such a way that all the graphs constructed along the way are prime induced subgraphs of G. A simplicial clique in G is a nonempty clique K such that for every k is an element of K the set of neighbors of k in V (G) \ K is a clique. Our second result is that a prime claw-free graph G has at most vertical bar V(G)vertical bar + 1 simplicial cliques, and we give an algorithm to find them all with running time O(vertical bar V (G)vertical bar(4)). In particular, this answers a question of Prasad Tetali [private communication] who asked if there is an efficient algorithm to test if a claw-free graph has a simplicial clique. Finally, we apply our results to claw-free graphs that are not prime. Such a graph may have exponentially many simplicial cliques, so we cannot list them all in polynomial time, but we can in a sense describe them. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1137/100817255 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
prime graphs,induced subgraphs,splitter theorem,claw-free graphs,simplicial clique | Prime (order theory),Complete bipartite graph,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Clique,Induced subgraph,Isomorphism,Mathematics | Journal |
Volume | Issue | ISSN |
26 | 2 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Chudnovsky | 1 | 390 | 46.13 |
| Paul D. Seymour | 2 | 2786 | 314.49 |