We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Clique-width for graph classes closed under complementation.

Blanché, A. and Dabrowski, K.K. and Johnson, M. and Lozin, V.V. and Paulusma, D. and Zamaraev, V. (2020) 'Clique-width for graph classes closed under complementation.', SIAM journal on discrete mathematics., 34 (2). pp. 1107-1147.


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

Item Type:Article
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
Full text:(VoR) Version of Record
Download PDF
Publisher Web site:
Publisher statement:© 2020 Society for Industrial and Applied Mathematics.
Date accepted:03 February 2020
Date deposited:05 February 2020
Date of first online publication:05 May 2020
Date first made open access:15 May 2020

Save or Share this output

Look up in GoogleScholar