Clique-width of graph classes defined by two forbidden induced subgraphs

Dabrowski, K. K.; Paulusma, D.

Abstract

The class of H-free graphs has bounded clique-width if and only if H is an induced subgraph of the 4-vertex path P4. We study the (un)boundedness of the clique-width of graph classes defined by two forbidden induced subgraphs H1 and H2. Prior to our study, it was not known whether the number of open cases was finite. We provide a positive answer to this question. To reduce the number of open cases, we determine new graph classes of bounded clique-width and new graph classes of unbounded clique-width. For obtaining the latter results, we first present a new, generic construction for graph classes of unbounded clique-width. Our results settle the boundedness or unboundedness of the clique-width of the class of (H1,H2)-free graphs for all pairs (H1,H2), both of which are connected, except two non-equivalent cases, and for all pairs (H1,H2), at least one of which is not connected, except 11 non-equivalent cases. We also consider classes characterized by forbidding a finite family of graphs {H1,…,Hp} as subgraphs, minors and topological minors, respectively, and completely determine which of these classes have bounded clique-width. Finally, we show algorithmic consequences of our results for the graph colouring problem restricted to (H1,H2)-free graphs.

Citation

Dabrowski, K. K., & Paulusma, D. (2016). Clique-width of graph classes defined by two forbidden induced subgraphs. The Computer Journal, 59(5), 650-666. https://doi.org/10.1093/comjnl/bxv096

• Journal Article Type: Article
• Acceptance Date: Oct 12, 2015
• Online Publication Date: May 9, 2016
• Publication Date: 2016-05
• Deposit Date: Nov 2, 2015
• Publicly Available Date: Nov 4, 2016
• Journal: The Computer Journal
• Print ISSN: 0010-4620
• Electronic ISSN: 1460-2067
• Publisher: BCS, The Chartered Institute for IT
• Peer Reviewed: Peer Reviewed
• Volume: 59
• Issue: 5
• Pages: 650-666
• DOI: https://doi.org/10.1093/comjnl/bxv096
• Keywords: Clique-width, Forbidden induced subgraph, Graph class.
• Public URL: https://durham-repository.worktribe.com/output/1427533