Publication detailsDabrowski, K.K., Masařík, T., Novotná, J., Paulusma, D. & Rzążewski, P. (2020), Clique-Width: Harnessing the Power of Atoms, in Adler, I. & Müller, H. eds, Lecture Notes in Computer Science 12301: WG 2020. Leeds, England, Springer, Cham, 119-133.
- Publication type: Conference Paper
- ISSN/ISBN: 0302-9743, 1611-3349, 9783030604394, 9783030604400
- DOI: 10.1007/978-3-030-60440-0_10
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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 if they are so on the atoms (graphs with no clique cut-set) of 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 (H1,H2) -free if it is both H1 -free and H2 -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 (H1,H2) -free graphs, as evidenced by one known example. We prove the existence of another such pair (H1,H2) and classify the boundedness of clique-width on (H1,H2) -free atoms for all but 18 cases.