Skip to main content

Research Repository

Advanced Search

Clique-width for graph classes closed under complementation

Blanché, A.; Dabrowski, K.K.; Johnson, M.; Lozin, V.V.; Paulusma, D.; Zamaraev, V.

Clique-width for graph classes closed under complementation Thumbnail


Authors

A. Blanché

K.K. Dabrowski

V.V. Lozin

V. Zamaraev



Abstract

Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite) set H of forbidden induced subgraphs. We study the boundedness of clique-width of hereditary graph classes closed under complementation. First, we extend the known classification for the |H| = 1 case by classifying the boundedness of clique-width for every set H of self-complementary graphs. We then completely settle the |H| = 2 case. In particular, we determine one new class of (H, H)-free graphs of bounded clique-width (as a side effect, this leaves only five classes of (H1, H2)-free graphs, for which it is not known whether their clique-width is bounded). Once we have obtained the classification of the |H| = 2 case, we research the effect of forbidding self-complementary graphs on the boundedness of clique-width. Surprisingly, we show that for every set F of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width for ({H, H} ∪ F)-free graphs coincides with the one for the |H| = 2 case if and only if F does not include the bull

Citation

Blanché, A., Dabrowski, K., Johnson, M., Lozin, V., Paulusma, D., & Zamaraev, V. (2020). Clique-width for graph classes closed under complementation. SIAM Journal on Discrete Mathematics, 34(2), 1107-1147. https://doi.org/10.1137/18m1235016

Journal Article Type Article
Acceptance Date Feb 3, 2020
Online Publication Date May 5, 2020
Publication Date 2020
Deposit Date Feb 4, 2020
Publicly Available Date May 15, 2020
Journal SIAM Journal on Discrete Mathematics
Print ISSN 0895-4801
Electronic ISSN 1095-7146
Publisher Society for Industrial and Applied Mathematics
Peer Reviewed Peer Reviewed
Volume 34
Issue 2
Pages 1107-1147
DOI https://doi.org/10.1137/18m1235016
Public URL https://durham-repository.worktribe.com/output/1308918

Files

Published Journal Article (559 Kb)
PDF

Copyright Statement
© 2020 Society for Industrial and Applied Mathematics.





You might also like



Downloadable Citations