Clique-width for graph classes closed under complementation

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

doi:10.1137/18m1235016

Clique-width for graph classes closed under complementation

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

Authors

A. Blanché

K.K. Dabrowski

Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department

V.V. Lozin

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

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