Publication detailsBrandstädt, A., Dabrowski, K.K., Huang, S. & Paulusma, D. (2015), Bounding the clique-width of H-free split graphs, Electronic Notes in Discrete Mathematics 49: The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015. Bergen, Norway, Elsevier, Bergen, 497-503.
- Publication type: Conference Paper
- ISSN/ISBN: 1571-0653
- DOI: 10.1016/j.endm.2015.06.069
- Keywords: Clique-width, Split graphs, Perfect graphs, Forbidden induced subgraph, Hereditary graph class.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.
Conference dates: August 31 — September 4, 2015