A. Blanché
Clique-Width for Graph Classes Closed under Complementation
Blanché, A.; Dabrowski, K. K.; Johnson, M.; Lozin, V. V.; Paulusma, D.; Zamaraev, V.
Authors
K. K. Dabrowski
Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
V. V. Lozin
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
V. Zamaraev
Contributors
Kim G. Larsen
Editor
Hans L. Bodlaender
Editor
Jean-Francois Raskin
Editor
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). Clique-Width for Graph Classes Closed under Complementation. In K. G. Larsen, H. L. Bodlaender, & J. Raskin (Eds.), 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) : August 21-25, 2017, Aalborg (Denmark) ; proceedings. https://doi.org/10.4230/lipics.mfcs.2017.73
Conference Name | 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS). |
---|---|
Conference Location | Aalborg, Denmark |
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 |
Files
Accepted Conference Proceeding
(567 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma and Viktor Zamaraev; licensed under Creative Commons License CC-BY
You might also like
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Independent transversals versus transversals
(2019)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search