# Properties and Recognition of Atom Graphs
## 4 Atom Graphs Are Perfect  
The clique graph of a chordal graph is not necessarily chordal, and not even perfect. For instance, the clique graph of the 5-sun is non-perfect, but its atom graph is chordal (see Figure 1), which follows from Characterization 14 below since the minimal separators of the 5-sun are pairwise non-inclusive. Introducing inclusion-comparable minimal separators, we can build a graph whose atom graph is non-chordal, as shown in Figure 2. This non-chordal atom graph is perfect though. We will show that each atom graph is perfect, and more accurately, that it is odd-hole-free and anti-hole-free. **Notation 1**. : _Let \(G=(V,E)\) be a graph. For each atom \(A\) and each clique \(S\) of \(G\) distinct from \(A\), \(C_{S}(A)\) denotes the connected component of \(G(V\setminus S)\) containing \(A\setminus S\)._  
This definition is correct since by definition of an atom, for each atom \(A\) and each clique \(S\) of \(G\) distinct from \(A\)\(G(A\setminus S)\) is necessarily non-empty and connected. In particular  
Figure 1: A chordal graph, its non-perfect clique graph and its chordal atom graph. Figure 2: A chordal graph, its chordal clique graph and its non-chordal (but perfect) atom graph. \(C_{S}(A)\) is defined if \(S\) is in the form \(X\cap Y\) where \(X\) and \(Y\) are distinct atoms of \(G\). Note that in that case, by Property 2, \(XY\) is an edge of \(AG(G)\) if and only if \(C_{S}(X)\
eq C_{S}(Y)\). Lemma 1: _Let \(A\) be an atom and \(S\) a clique of a graph \(G\) such that \(S\subset A\). Then \(S=N_{G}(C_{S}(A))\)._  
Proof: \(N_{G}(C_{S}(A))\) is clearly a subset of \(S\), and it cannot be a strict subset of \(S\) since in that case it would be a clique \(ab\)-separator of \(G(A)\) for any \(a\) in \(A\setminus S\) and any \(b\) in \(S\setminus N_{G}(C_{S}(A))\). Lemma 2: _Let \(G\) be a graph, let \(\mu\) be a cycle of \(AG(G)\), let \(AB\) be an edge of \(\mu\) and let \(S=A\cap B\); then there is an edge \(A^{\prime}B^{\prime}\) of \(\mu\) such that \(C_{S}(B)=C_{S}(B^{\prime})\) and \(A^{\prime}\cap B^{\prime}\subseteq S\), with \(A\), \(B\), \(B^{\prime}\), \(A^{\prime}\) in this order on \(\mu\) (with possibly \(B=B^{\prime}\) or \(A^{\prime}=A\))._  
Proof: As \(AB\) is an edge of \(AG(G)\), \(C_{S}(A)\
eq C_{S}(B)\). Let \(A^{\prime}\) be the first node \(X\) of the path \(\mu-\{AB\}\) from \(B\) such that \(C_{S}(X)\
eq C_{S}(B)\), and let \(B^{\prime}\) be the node preceding \(A^{\prime}\) on this path from \(B\). \(C_{S}(B)=C_{S}(B^{\prime})\) with \(A\), \(B\), \(B^{\prime}\), \(A^{\prime}\) in this order on \(\mu\), and as \(C_{S}(A^{\prime})\
eq C_{S}(B)\), it follows that \(C_{S}(A^{\prime})\
eq C_{S}(B^{\prime})\), and therefore \(A^{\prime}\cap B^{\prime}\subseteq S\). We deduce from Lemma 2 the following properties of atom graphs. Property 8 is proved in [18] for chordal graphs. Property 7: _Let \(G\) be a graph, let \(\mu\) be a cycle of \(AG(G)\) and let \(S\) be an inclusion-minimal set among the sets associated with the edges of \(\mu\); then \(S\) is associated with at least two edges of \(\mu\)._  
Property 8: _Let \(G\) be a graph and let \(\mu\) be a \(C_{3}\) of \(AG(G)\); then two of the clique minimal separators associated with the edges of \(\mu\) are equal and included in the third one._  
Lemma 3: _Let \(G\) be a connected graph, let \(X\), \(X^{\prime}\) and \(Y\) be atoms and let \(S\) be the intersection of two distinct atoms of \(G\)._  
_(a) If_ \(S\subseteq X\) _and_ \(C_{S}(X)\
eq C_{S}(Y)\) _then (_\(XY\) _is an edge of_ \(AG(G)\Leftrightarrow N(C_{S}(Y))\subseteq Y\)_),_  
_(b) If_ \(S\subseteq X\cap Y\) _and_ \(C_{S}(X)\
eq C_{S}(Y)\) _then_ \(XY\) _is an edge of_ \(AG(G)\)_,_  
_(c) If_ \(S\subseteq X\cap X^{\prime}\)_,_ \(C_{S}(X)=C_{S}(X^{\prime})\) _and_ \(Y\) _is adjacent to_ \(X\) _but not to_ \(X^{\prime}\) _in_ \(AG(G)\) _then_ \(C_{S}(X)=C_{S}(Y)\)_._  
Proof: (a) Let \(G=(V,E)\). We assume that \(S\subseteq X\) and \(C_{S}(X)\
eq C_{S}(Y)\). Let us show that \(XY\) is an edge of \(AG(G)\Leftrightarrow N(C_{S}(Y))\subseteq Y\).