Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Clique-width : harnessing the power of atoms.

Dabrowski, K.K. and Masařík, T. and Novotná, J. and Paulusma, D. and Rzążewski, P. (2020) 'Clique-width : harnessing the power of atoms.', in Graph-theoretic concepts in computer science: 46th International Workshop, WG 2020, Leeds, UK, June 24–26, 2020, revised selected papers. Cham: Springer, pp. 119-133. Lecture notes in computer science., 2301

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.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
(409Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1007/978-3-030-60440-0_10
Publisher 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
Date accepted:15 July 2020
Date deposited:16 July 2020
Date of first online publication:October 2020
Date first made open access:01 December 2020

Save or Share this output

Export:
Export
Look up in GoogleScholar