Clique-Width for Graph Classes Closed under Complementation

Blanché, A.; Dabrowski, K. K.; Johnson, M.; Lozin, V. V.; Paulusma, D.; Zamaraev, V.

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.

Citation

Blanché, A., Dabrowski, K. K., Johnson, M., Lozin, V. V., Paulusma, D., & Zamaraev, V. (2017, August). Clique-Width for Graph Classes Closed under Complementation. Presented at 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS)., Aalborg, Denmark

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS).
• Start Date: Aug 21, 2017
• End Date: Aug 25, 2017
• Acceptance Date: Jun 12, 2017
• Publication Date: Dec 1, 2017
• Deposit Date: Jul 2, 2017
• Publicly Available Date: Jul 3, 2017
• Series Title: LIPIcs–Leibniz International Proceedings in Informatics
• Series Number: 83
• Series ISSN: 1868-8969
• Book Title: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings.
• DOI: https://doi.org/10.4230/lipics.mfcs.2017.73
• Public URL: https://durham-repository.worktribe.com/output/1146723