Blanché, Alexandre ;
Dabrowski, Konrad K. ;
Johnson, Matthew ;
Lozin, Vadim V. ;
Paulusma, Daniël ;
Zamaraev, Viktor
CliqueWidth for Graph Classes Closed under Complementation
Abstract
Cliquewidth 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 cliquewidth of hereditary graph classes closed under complementation. First, we extend the known classification for the H=1 case by classifying the boundedness of cliquewidth for every set H of selfcomplementary 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 cliquewidth (as a side effect, this leaves only six classes of (H1, H2)free graphs, for which it is not known whether their cliquewidth is bounded).
Once we have obtained the classification of the H=2 case, we research the effect of forbidding selfcomplementary graphs on the boundedness of cliquewidth. Surprisingly, we show that for a set F of selfcomplementary graphs on at least five vertices, the classification of the boundedness of cliquewidth 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 nonempty selfcomplementary graphs on fewer than five vertices are P_1 and P_4, and P_4free graphs have cliquewidth at most 2).
Finally, we discuss the consequences of our results for COLOURING.
BibTeX  Entry
@InProceedings{blanch_et_al:LIPIcs:2017:8075,
author = {Alexandre Blanch{\'e} and Konrad K. Dabrowski and Matthew Johnson and Vadim V. Lozin and Dani{\"e}l Paulusma and Viktor Zamaraev},
title = {{CliqueWidth for Graph Classes Closed under Complementation}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {73:173:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8075},
URN = {urn:nbn:de:0030drops80756},
doi = {10.4230/LIPIcs.MFCS.2017.73},
annote = {Keywords: cliquewidth, selfcomplementary graph, forbidden induced subgraph}
}
2017
Keywords: 

cliquewidth, selfcomplementary graph, forbidden induced subgraph 
Seminar: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Issue date: 

2017 
Date of publication: 

2017 