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. (2015, November). Bounding the clique-width of H-free split graphs. Presented at European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),, Bergen, Norway

• Presentation Conference Type: Conference Paper (published)
• Conference Name: European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),
• Publication Date: Nov 12, 2015
• Deposit Date: Aug 12, 2015
• Publicly Available Date: Nov 12, 2016
• Volume: 49
• Pages: 497-503
• Series Title: Electronic Notes in Discrete Mathematics
• Series ISSN: 1571-0653
• DOI: https://doi.org/10.1016/j.endm.2015.06.069
• Keywords: Clique-width, Split graphs, Perfect graphs, Forbidden induced subgraph, Hereditary graph class.
• Public URL: https://durham-repository.worktribe.com/output/1152202
• Additional Information: Conference dates: August 31 — September 4, 2015