License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.73
URN: urn:nbn:de:0030-drops-80756
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8075/
Go to the corresponding LIPIcs Volume Portal

Blanché, Alexandre ; Dabrowski, Konrad K. ; Johnson, Matthew ; Lozin, Vadim V. ; Paulusma, Daniël ; Zamaraev, Viktor

Clique-Width for Graph Classes Closed under Complementation

pdf-format:
LIPIcs-MFCS-2017-73.pdf (0.5 MB)

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.

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 =	{{Clique-Width for Graph Classes Closed under Complementation}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{73:1--73:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8075},
  URN =		{urn:nbn:de:0030-drops-80756},
  doi =		{10.4230/LIPIcs.MFCS.2017.73},
  annote =	{Keywords: clique-width, self-complementary graph, forbidden induced subgraph}
}

Keywords: clique-width, self-complementary graph, forbidden induced subgraph
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI