Skip to main content

Research Repository

Advanced Search

Clique-Width: Harnessing the Power of Atoms

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

Clique-Width: Harnessing the Power of Atoms Thumbnail


Authors

K. K. Dabrowski

T. Masařík

J. Novotná

P. Rzążewski



Contributors

I. Adler
Editor

H. Müller
Editor

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). Clique-Width: Harnessing the Power of Atoms. In I. Adler, & H. Müller (Eds.), Graph-theoretic concepts in computer science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, revised selected papers (119-133). https://doi.org/10.1007/978-3-030-60440-0_10

Conference Name WG 2020
Conference Location Leeds, England
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 Mar 28, 2024
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

Files

Accepted Conference Proceeding (418 Kb)
PDF

Copyright Statement
This is a post-peer-review, pre-copyedit version of an article published in Graph-theoretic concepts in computer science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, revised selected papers. The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-60440-0_10





You might also like



Downloadable Citations