Clique-Width for Graph Classes Closed under Complementation



Blanché, Alexandre, Dabrowski, Konrad K, Johnson, Matthew, Lozin, Vadim V, Paulusma, Daniël and Zamaraev, Viktor ORCID: 0000-0001-5755-4141
(2020) Clique-Width for Graph Classes Closed under Complementation. SIAM Journal on Discrete Mathematics, 34 (2). pp. 1107-1147.

[img] Text
Clique-width.pdf - Submitted version

Download (585kB) | Preview

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 ℋ 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 |ℋ| = 1 case by classifying the boundedness of clique-width for every set ℋ of self-complementary graphs. We then completely settle the |ℋ| = 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 |ℋ| = 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 |ℋ| = 2 case if and only if F does not include the bull.

Item Type: Article
Uncontrolled Keywords: clique-width, hereditary graph class, dichotomy
Depositing User: Symplectic Admin
Date Deposited: 06 Jul 2020 10:48
Last Modified: 18 Jan 2023 23:47
DOI: 10.1137/18m1235016
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3092250