DIKUL - logo
E-resources
Full text
Peer reviewed
  • Growing Without Cloning
    Chudnovsky, Maria; Seymour, Paul

    SIAM journal on discrete mathematics, 01/2012, Volume: 26, Issue: 2
    Journal Article

    A graph $G$ is claw-free if no induced subgraph of it is isomorphic to the complete bipartite graph $K_{1,3}$, and it is prime if $|V(G)| \geq 4$ and there is no $X \subseteq V(G)$ with $1<|X|<|V(G)|$ such that every vertex of $V(G) \setminus 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 \in K$ the set of neighbors of $k$ in $V(G) \setminus K$ is a clique. Our second result is that a prime claw-free graph $G$ has at most $|V(G)|+1$ simplicial cliques, and we give an algorithm to find them all with running time $O(|V(G)|^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. PUBLICATION ABSTRACT