Clique-width: Harnessing the power of atoms

Many NP-complete graph problems are polynomial-time solvable on graph classes of bounded clique-width. Several of these problems are polynomial-time solvable on a hereditary graph class G ${\mathscr{G}}$ if they are so on the atoms (graphs with no clique cut-set) of G ${\mathscr{G}}$. Hence, we initiate a systematic study into boundedness of clique-width of atoms of hereditary graph classes. A graph G $G$ is H $H$-free if H $H$ is not an induced subgraph of G $G$, and it is (H1,H2) $({H}_{1},{H}_{2})$-free if it is both H1 ${H}_{1}$-free and H2 ${H}_{2}$-free. A class of H $H$-free graphs has bounded clique-width if and only if its atoms have this property. This is no longer true for (H1,H2) $({H}_{1},{H}_{2})$-free graphs, as evidenced by one known example. We prove the existence of another such pair (H1,H2) $({H}_{1},{H}_{2})$ and classify the boundedness of clique-width on (H1,H2) $({H}_{1},{H}_{2})$-free atoms for all but 18 cases.