Skip to main content

Research Repository

Advanced Search

Bounding the clique-width of H-free split graphs

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

Authors

A. Brandstädt

K.K. Dabrowski

S. Huang



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). Bounding the clique-width of H-free split graphs. . https://doi.org/10.1016/j.endm.2015.06.069

Conference Name European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2015),
Conference Location Bergen, Norway
Publication Date Nov 12, 2015
Deposit Date Aug 12, 2015
Publicly Available Date Mar 29, 2024
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

Files





You might also like



Downloadable Citations