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 of graph classes defined by two forbidden induced subgraphs.

Dabrowski, K.K. and Paulusma, D. (2015) 'Clique-width of graph classes defined by two forbidden induced subgraphs.', The computer journal. .

Abstract

The class of H-free graphs has bounded clique-width if and only if H is an induced subgraph of the 4-vertex path P4. We study the (un)boundedness of the clique-width of graph classes defined by two forbidden induced subgraphs H1 and H2. Prior to our study, it was not known whether the number of open cases was finite. We provide a positive answer to this question. To reduce the number of open cases, we determine new graph classes of bounded clique-width and new graph classes of unbounded clique-width. For obtaining the latter results, we first present a new, generic construction for graph classes of unbounded clique-width. Our results settle the boundedness or unboundedness of the clique-width of the class of (H1,H2)-free graphs for all pairs (H1,H2), both of which are connected, except two non-equivalent cases, and for all pairs (H1,H2), at least one of which is not connected, except 11 non-equivalent cases. We also consider classes characterized by forbidding a finite family of graphs {H1,…,Hp} as subgraphs, minors and topological minors, respectively, and completely determine which of these classes have bounded clique-width. Finally, we show algorithmic consequences of our results for the graph colouring problem restricted to (H1,H2)-free graphs.

Item Type:Article
Keywords:Clique-width, Forbidden induced subgraph, Graph class.
Full text:(AM) Accepted Manuscript
Download PDF
(374Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1093/comjnl/bxv096
Publisher statement:This is a pre-copyedited, author-produced PDF of an article accepted for publication in The Computer Journal following peer review. The version of record Dabrowski, K.K. and Paulusma, D. (2015) 'Clique-width of graph classes defined by two forbidden induced subgraphs.', The computer journal, first published online: November 4, 2015 is available online at: http://dx.doi.org/10.1093/comjnl/bxv096.
Date accepted:12 October 2015
Date deposited:09 November 2015
Date of first online publication:2015
Date first made open access:04 November 2016

Save or Share this output

Export:
Export
Look up in GoogleScholar