2026-07-20T11:15:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8075 2024-03-06T10:40:58Z ddc:004 open_access

Clique-Width for Graph Classes Closed under Complementation Blanché, Alexandre Dabrowski, Konrad K. Johnson, Matthew Lozin, Vadim V. Paulusma, Daniël Zamaraev, Viktor clique-width self-complementary graph forbidden induced subgraph 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 initiate a systematic study into 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 (H1, complement of H1)-free graphs of bounded clique-width (as a side effect, this leaves only six 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 a set F of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width for ({H1, complement of H1} + F)-free graphs coincides with the one for the |H|=2 case if and only if F does not include the bull (the only non-empty self-complementary graphs on fewer than five vertices are P_1 and P_4, and P_4-free graphs have clique-width at most 2). Finally, we discuss the consequences of our results for COLOURING. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexandre Blanché and Konrad K. Dabrowski and Matthew Johnson and Vadim V. Lozin and Daniël Paulusma and Viktor Zamaraev 2017 Is Part Of LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2017.73 urn:nbn:de:0030-drops-80756 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.73 eng https://creativecommons.org/licenses/by/3.0/legalcode