Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Research & business

View Profile

Publication details

Brandstä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.

Author(s) from Durham

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.

Notes

Conference dates: August 31 — September 4, 2015