Bounding clique-width via perfect graphs

Dabrowski, K. K.; Huang, S.; Paulusma, D.

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.

Citation

Dabrowski, K. K., Huang, S., & Paulusma, D. (2015, March). Bounding clique-width via perfect graphs. Presented at International Conference on Language and Automata Theory and Applications, Nice, France

• Presentation Conference Type: Conference Paper (published)
• Conference Name: International Conference on Language and Automata Theory and Applications
• Start Date: Mar 2, 2015
• End Date: Mar 6, 2015
• Publication Date: Feb 24, 2015
• Deposit Date: Dec 20, 2014
• Publicly Available Date: Feb 24, 2016
• Print ISSN: 0302-9743
• Pages: 676-688
• Series Title: Lecture notes in computer science
• Series Number: 8977
• Series ISSN: 0302-9743
• Book Title: Language and automata theory and applications : 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015 ; proceedings.
• ISBN: 9783319155784
• DOI: https://doi.org/10.1007/978-3-319-15579-1_53
• Keywords: Clique-width, Forbidden induced subgraphs, Graph class.
• Public URL: https://durham-repository.worktribe.com/output/1154558