Clique-Width: Harnessing the Power of Atoms

Dabrowski, K. K.; Masařík, T.; Novotná, J.; Paulusma, D.; Rzążewski, P.

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 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.

Citation

Dabrowski, K. K., Masařík, T., Novotná, J., Paulusma, D., & Rzążewski, P. (2020, June). Clique-Width: Harnessing the Power of Atoms. Presented at WG 2020, Leeds, England

• Presentation Conference Type: Conference Paper (published)
• Conference Name: WG 2020
• Start Date: Jun 24, 2020
• End Date: Jun 26, 2020
• Acceptance Date: Jul 15, 2020
• Publication Date: 2020
• Deposit Date: Jul 10, 2020
• Publicly Available Date: Dec 1, 2020
• Print ISSN: 0302-9743
• Volume: 2301
• Pages: 119-133
• Series Title: Lecture notes in computer science
• Series ISSN: 0302-9743,1611-3349
• Book Title: Graph-theoretic concepts in computer science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, revised selected papers.
• ISBN: 9783030604394
• DOI: https://doi.org/10.1007/978-3-030-60440-0_10
• Public URL: https://durham-repository.worktribe.com/output/1140444