Given two graphs H_1 and H_2, a graph G is (H_1, H_2)-free if it contains no subgraph isomorphic to H_1 or H_2. We continue a recent study into the clique-width of (H_1, H_2)-free graphs and present three new classes of (H_1, H_2)-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 (H_1, H_2)-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.
展开▼
