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:

Bounding clique-width via perfect graphs.

Dabrowski, K.K. and Huang, S. and Paulusma, D. (2015) 'Bounding clique-width via perfect graphs.', in Language and automata theory and applications : 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015 ; proceedings. , pp. 676-688. Lecture notes in computer science. (8977).

Abstract

Given two graphs H1 and H2, a graph G is (H1,H2)-free if it contains no subgraph isomorphic to H1 or H2. We continue a recent study into the clique-width of (H1,H2)-free graphs and present three new classes of (H1,H2)-free graphs that have bounded clique-width. We also show the implications of our results for the computational complexity of the Colouring problem restricted to (H1,H2)-free graphs. The three new graph classes have in common that one of their two forbidden induced subgraphs is the diamond (the graph obtained from a clique on four vertices by deleting one edge). To prove boundedness of their clique-width we develop a technique based on bounding clique covering number in combination with reduction to subclasses of perfect graphs.

Item Type:Book chapter
Keywords:Clique-width, Forbidden induced subgraphs, Graph class.
Full text:(AM) Accepted Manuscript
Download PDF
(424Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1007/978-3-319-15579-1_53
Publisher statement:The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-15579-1_53.
Date accepted:No date available
Date deposited:20 January 2015
Date of first online publication:2015
Date first made open access:24 February 2016

Save or Share this output

Export:
Export
Look up in GoogleScholar