Clique-width for graph classes closed under complementation

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

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