# Properties and Recognition of Atom Graphs
## 1 Introduction  
Decomposition by clique separators was introduced by [PERSON] [1] in 1985 to help the resolution of hard problems. This decomposition of a graph \(G\) can be represented by a binary tree whose nodes are vertex subsets of \(G\). Its root is the vertex set of \(G\), and for each node \(V^{\prime}\), if \(G(V^{\prime})\) has a clique separator then the node \(V^{\prime}\) has two children \(A\cup S\) and \(B\cup S\), where \(\{A,B,S\}\) is a partition of \(V^{\prime}\) and \(S\) is a clique \(AB\)-separator, otherwise, \(V^{\prime}\) is a leaf of the tree and is called an _atom_. However, the set of atoms depends on the choice of the clique separators. [PERSON] [2] proved that the set of atoms is uniquely defined if the set \(S\) is a clique _minimal_\(AB\)-separator in the definition above, leading to the notion of _clique minimal separator decomposition_.  
Clique minimal separator decomposition has been studied in different contexts. A general survey is given in [3], and the complexity of its computation is improved in [4]. This decomposition is investigated in some particular graph classes [5; 6; 7; 8; 9; 10] and is used in the domains of databases [11], text mining [12], and biology [13; 14].  
The atoms of a chordal graph are its maximal cliques. Several graphs are defined from a connected chordal graph \(G\), whose nodes are the maximal cliques of \(G\): its _clique trees_[15; 16], its _clique graph_[17], which is the intersection graph of its maximal cliques, and the union of its clique trees, which is a subgraph of its clique graph and is shown to better capture the structure of \(G\) than its clique graph [18; 19].  
These graphs, defined from a connected chordal graph, can be generalized to any connected graph \(G\), whose nodes are the atoms of \(G\): its _atom trees_[20] and its _atom graph_, which is the union of its atom trees and a subgraph of the intersection graph of its atoms, which better captures the structure of \(G\) than the intersection graph of its atoms. Hence, the atom trees of a connected chordal graph are its clique trees, and its atom graph is a subgraph of its clique graph.  
The notion of atom graph was introduced in 2007 in [14] to visualize biological clusters. Several algorithms computing the atom graph of a graph are presented in [21] and extended to the computation of the union join tree of an \(\alpha\)-acyclic hypergraph.  
In this paper, we focus on the class of atom graphs. A graph \(G\) is an atom graph if there is a graph whose atom graph is isomorphic to \(G\). First of all, we deduce from known results that the atom graphs are exactly the atom graphs of chordal graphs, which is not the case for clique graphs. We prove that each atom graph is a _perfect_ graph, i.e., a graph such that each induced subgraph has the same chromatic and clique number, or equivalently (Strong Perfect Graph Theorem), a graph having no induced odd hole nor induced odd anti-hole. We give a characterization of an atom graph in terms of a spanning tree, leading to an algorithm recognizing an atom graph in \(O(m^{n-1}n^{5})\) time. We also define two graph classes such that the atom graphs of the graphs of these classes can be recognized in linear time.  
The paper is organized as follows. Section 2 provides some preliminaries. Section 3 characterizes an atom graph as an atom graph of a chordal graph. Section 4 proves that each atom graph is perfect. Section 5 characterizes the chordal graphs having the same atom and clique graph. Sections 6 and 7 provide characterizations of an atom graph in terms of a hypergraph and a spanning tree, respectively. Section 8 investigates the atom graphs of the graphs of two graph classes. We conclude in Section 9.