Clique-Width: Harnessing the Power of Atoms

Abstract

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 $\mathcal{G}$ if they are so on the atoms (graphs with no clique cut-set) of $\mathcal{G}$. Hence, we initiate a systematic study into boundedness of clique-width of atoms of hereditary graph classes. A graph $G$ is $H$-free if $H$ is not an induced subgraph of $G$, and it is $(H_1,H_2)$-free if it is both $H_1$-free and $H_2$-free. A class of $H$-free graphs has bounded clique-width if and only if its atoms have this property. This is no longer true for $(H_1,H_2)$-free graphs, as evidenced by one known example. We prove the existence of another such pair $(H_1,H_2)$ and classify the boundedness of clique-width on $(H_1,H_2)$-free atoms for all but 18 cases.

37 pages, 32 figures, an extended abstract of this paper appeared in the proceedings of WG 2020

References in corpus (4)

• Graph Operations on Clique-Width Bounded Graphs
• Clique-Width for Hereditary Graph Classes
• Bounding the Mim-Width of Hereditary Graph Classes
• On graphs with no induced five-vertex path or paraglider