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

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

Author(s) from Durham


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.