Characterizing Atoms that Result from Decomposition by Clique Separators

Abstract

A graph is defined to be an atom if no minimal vertex separator induces a complete subgraph; thus, atoms are the graphs that are immune to clique separator decomposition. Atoms are characterized here in two ways: first using generalized vertex elimination schemes, and then as generalizations of 2-connected unichord-free graphs (the graphs in which every minimal vertex separator induces an edgeless subgraph).

Keywords

• clique separator
• minimal separator
• unichord-free graph
• 05c75
• 05c69
• 05c40