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.', in Algorithms and complexity : 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015 ; proceedings. , pp. 167-181. Lecture notes in computer science. (9079).

Abstract

If a graph has no induced subgraph isomorphic to any graph in a finite family {H1,…,Hp}, it is said to be (H1,…,Hp)-free. 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:Book chapter
Keywords:Clique-width, Forbidden induced subgraph, Graph class
Full text:(AM) Accepted Manuscript
Download PDF
(477Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1007/978-3-319-18173-8_12
Publisher statement:The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-18173-8_12.
Date accepted:No date available
Date deposited:20 January 2015
Date of first online publication:May 2015
Date first made open access:16 May 2016

Save or Share this output

Export:
Export
Look up in GoogleScholar