Summary: 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 \(\mathcal{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 \(|\mathcal{H}|=1\) case by classifying the boundedness of clique-width for every set \(\mathcal{H}\) of self-complementary graphs. We then completely settle the \(|\mathcal{H}|=2\) case. In particular, we determine one new class of \((H,\overline{H})\)-free graphs of bounded clique-width (as a side effect, this leaves only six classes of \((H_1,H_2)\)-free graphs, for which it is not known whether their clique-width is bounded). Once we have obtained the classification of the \(|\mathcal{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 \(\mathcal{F}\) of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width for \((\{H,\overline{H}\}\cup\mathcal{F})\)-free graphs coincides with the one for the \(|\mathcal{H}|=2\) case if and only if \(\mathcal{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.
For the entire collection see [Zbl 1376.68011].