Bounding the clique-width of H-free split graphs

Brandstädt, A.; Dabrowski, K.K.; Huang, S.; Paulusma, D.

Abstract

A graph is H-free if it has no induced subgraph isomorphic to H. We continue a study into the boundedness of clique-width of subclasses of perfect graphs. We identify five new classes of H-free split graphs whose clique-width is bounded. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H-free split graphs has bounded clique-width.

Citation

Brandstädt, A., Dabrowski, K., Huang, S., & Paulusma, D. (2016). Bounding the clique-width of H-free split graphs. Discrete Applied Mathematics, 211, 30-39. https://doi.org/10.1016/j.dam.2016.04.003

• Journal Article Type: Article
• Acceptance Date: Apr 6, 2016
• Online Publication Date: May 6, 2016
• Publication Date: Oct 1, 2016
• Deposit Date: May 17, 2016
• Publicly Available Date: May 6, 2017
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 211
• Pages: 30-39
• DOI: https://doi.org/10.1016/j.dam.2016.04.003
• Public URL: https://durham-repository.worktribe.com/output/1381705