<p>Chvátal and Sbihi (Recognizing Claw-free Perfect Graphs, JCTB 44) described the atoms for the class of claw-free perfect graphs, a.k.a. quasi-line perfect graphs.  This description was later refined by Maffray and Reed, and essentially consists of two classes: "peculiar", which are kind of a special case, and "elementary", which are constructed by modifying the line graph of a bipartite multigraph through an operation called augmentation.</p>

CC BY-SA 3.0
2012-07-08T18:23:24.680Z
I am sure that I will find some more results by looking the publications of the same authors. Thank you.
Arman
CC BY-SA 3.0
2012-07-09T04:53:34.777Z
I should mention that there is another class of graphs, *clique-separable graphs*, whose atoms are the complete multipartite graphs and cliques joined to bipartite graphs.
Andrew D. King
CC BY-SA 3.0
2012-07-06T16:55:52.787Z
2012-07-06T16:55:52.787Z
Andrew D. King
<p>Tarjan described a procedure for decomposing a graph using clique separators in "Decomposition by clique separators", RE Tarjan - Discrete mathematics, 1985 - Elsevier. </p>

<p>He also proposed different divide-and-conquer algorithms for various graph problems such as maximum clique, minimum coloring and maximum independent set. An atom is a subgraph of a graph that does not contain a separator. If one can solve the problem efficiently in the atoms (local solutions) then Tarjan describes in the same paper how to extend these local solutions to a global solution. Therefore characterization of the atoms is very important. For example an atom of a chordal graph is a clique and the atoms of an edge intersection graphs of paths in a tree are exactly line graphs of a multigraph.</p>

<p>I am wondering the characterization of atoms for other graph classes like for example disk graphs or AT-free graphs.</p>

<ds.algorithms><graph-theory><graph-algorithms><separation>
Decomposition by Clique Separators
Arman
# Decomposition by Clique Separators

(Asked by: username_0 on 2012-06-30)

Tarjan described a procedure for decomposing a graph using clique separators in "Decomposition by clique separators", RE Tarjan - Discrete mathematics, 1985 - Elsevier.

He also proposed different divide-and-conquer algorithms for various graph problems such as maximum clique, minimum coloring and maximum independent set. An atom is a subgraph of a graph that does not contain a separator. If one can solve the problem efficiently in the atoms (local solutions) then Tarjan describes in the same paper how to extend these local solutions to a global solution. Therefore characterization of the atoms is very important. For example an atom of a chordal graph is a clique and the atoms of an edge intersection graphs of paths in a tree are exactly line graphs of a multigraph.

I am wondering the characterization of atoms for other graph classes like for example disk graphs or AT-free graphs.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, separation


---

## 1 answers

### Answer by username_1 on 2012-07-06. Score: 6 | Accepted answer

Chvátal and Sbihi (Recognizing Claw-free Perfect Graphs, JCTB 44) described the atoms for the class of claw-free perfect graphs, a.k.a. quasi-line perfect graphs. This description was later refined by Maffray and Reed, and essentially consists of two classes: "peculiar", which are kind of a special case, and "elementary", which are constructed by modifying the line graph of a bipartite multigraph through an operation called augmentation.

> **Comments:**
> **username_0**: I am sure that I will find some more results by looking the publications of the same authors. Thank you.  
> **username_1**: I should mention that there is another class of graphs, *clique-separable graphs*, whose atoms are the complete multipartite graphs and cliques joined to bipartite graphs.  

---

