@inproceedings { ,
title = {Clique-Width for Graph Classes Closed under Complementation},
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 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.},
conference = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS).},
doi = {10.4230/lipics.mfcs.2017.73},
note = {EPrint Processing Status: Full text deposited in DRO},
publicationstatus = {Published},
url = {https://durham-repository.worktribe.com/output/1146723},
keyword = {Algorithms and Complexity in Durham (ACiD)},
year = {2017},
author = {BlancheĢ, A. and Dabrowski, K. K. and Johnson, M. and Lozin, V. V. and Paulusma, D. and Zamaraev, V.}
editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}
}