6
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I am sure that I will find some more results by looking the publications of the same authors. Thank you. $\endgroup$
    – Arman
    Commented Jul 8, 2012 at 18:23
  • 2
    $\begingroup$ 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. $\endgroup$
    – Andrew D. King
    Commented Jul 9, 2012 at 4:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.