The Library
Clique-width for graph classes closed under complementation
Tools
Blanché, Alexandre, Dabrowski, Konrad, Johnson, Matthew, Lozin, Vadim V., Paulusma, Daniël and Zamaraev, Viktor (2020) Clique-width for graph classes closed under complementation. SIAM Journal on Discrete Mathematics, 34 (2). pp. 1107-1147. doi:10.1137/18M1235016 ISSN 0895-4801.
|
PDF
WRAP-clique-width-graph-classes-closed-complementation-Lozin-2020.pdf - Accepted Version - Requires a PDF viewer. Download (1249Kb) | Preview |
Official URL: https://doi.org/10.1137/18M1235016
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 ${\cal H}$ 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 $|{\cal H}|=1$ case by classifying the boundedness of clique-width for every set ${\cal H}$ of self-complementary graphs. We then completely settle the $|{\cal H}|=2$ case. In particular, we determine one new class of $(H,\overline{H})$-free graphs of bounded clique-width (as a side effect, this leaves only five classes of $(H_1,H_2)$-free graphs, for which it is not known whether their clique-width is bounded). Once we have obtained the classification of the $|{\cal H}|=2$ case, we research the effect of forbidding self-complementary graphs on the boundedness of clique-width. Surprisingly, we show that for every set ${\cal F}$ of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width for $(\{H,\overline{H}\}\cup {\cal F})$-free graphs coincides with the one for the $|{\cal H}|=2$ case if and only if ${\cal F}$ does not include the bull.
Item Type: | Journal Article | ||||||
---|---|---|---|---|---|---|---|
Alternative Title: | |||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||
Journal or Publication Title: | SIAM Journal on Discrete Mathematics | ||||||
Publisher: | Society for Industrial and Applied Mathematics | ||||||
ISSN: | 0895-4801 | ||||||
Official Date: | 5 May 2020 | ||||||
Dates: |
|
||||||
Volume: | 34 | ||||||
Number: | 2 | ||||||
Page Range: | pp. 1107-1147 | ||||||
DOI: | 10.1137/18M1235016 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Reuse Statement (publisher, data, author rights): | “First Published in SIAM Journal on Discrete Mathematics in 34,2. 2020, published by the Society for Industrial and Applied Mathematics (SIAM)” and the copyright notice as stated in the article itself (e.g., “Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.”) | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Copyright Holders: | © 2020, Society for Industrial and Applied Mathematics. Unauthorized reproduction of this article is prohibited. | ||||||
Date of first compliant deposit: | 19 March 2020 | ||||||
Date of first compliant Open Access: | 19 March 2020 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year