E-resources
Peer reviewed
-
Chudnovsky, Maria; Seymour, Paul
SIAM journal on discrete mathematics, 01/2012, Volume: 26, Issue: 2Journal 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
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|
Source: Personal bibliographies
and: SICRIS
The material is available in full text. If you wish to order the material anyway, click the Continue button.