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).
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)
|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
|Look up in GoogleScholar|