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.

$\endgroup$
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.

$\endgroup$
  • $\begingroup$ I am sure that I will find some more results by looking the publications of the same authors. Thank you. $\endgroup$ – Arman Jul 8 '12 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 Jul 9 '12 at 4:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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