Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

View Profile

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.

Author(s) from Durham

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.