Publication details

Dabrowski, K.K., Huang, S. & Paulusma, D. (2015), Bounding clique-width via perfect graphs, in Dediu, Adrian-Horia, Formenti, Enrico, Martín-Vide, Carlos & Truthe, Bianca eds, Lecture Notes in Computer Science 8977: International Conference on Language and Automata Theory and Applications. Nice, France, Springer, Nice, 676-688.

• Publication type: Conference Paper
• ISSN/ISBN: 9783319155784, 9783319155791, 0302-9743
• DOI: 10.1007/978-3-319-15579-1_53
• Keywords: Clique-width, Forbidden induced subgraphs, Graph class.
• Further publication details on publisher web site
• Durham Research Online (DRO) - may include full text

Author(s) from Durham

• Professor Daniel Paulusma
• Dr Konrad Dabrowski

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.