The Library
Infinitely many minimal classes of graphs of unbounded clique-width
Tools
Collins, A., Foniok, J., Korpelainen, Nicholas, Lozin, Vadim V. and Zamaraev, Victor (2018) Infinitely many minimal classes of graphs of unbounded clique-width. Discrete Applied Mathematics, 248 . pp. 145-152. doi:10.1016/j.dam.2017.02.012 ISSN 0166-218X.
|
PDF
WRAP-infinitely-many-minimal-classes-graphs-unbounded-Lozin-2017.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (624Kb) | Preview |
Official URL: https://doi.org/10.1016/j.dam.2017.02.012
Abstract
The celebrated theorem of Robertson and Seymour states that in the family of minor-closed graph classes, there is a unique minimal class of graphs of unbounded tree-width, namely, the class of planar graphs. In the case of tree-width, the restriction to minor-closed classes is justified by the fact that the tree-width of a graph is never smaller than the tree-width of any of its minors. This, however, is not the case with respect to clique-width, as the clique-width of a graph can be (much) smaller than the clique-width of its minor. On the other hand, the clique-width of a graph is never smaller than the clique-width of any of its induced subgraphs, which allows us to be restricted to hereditary classes (that is, classes closed under taking induced subgraphs), when we study clique-width. Up to date, only finitely many minimal hereditary classes of graphs of unbounded clique-width have been discovered in the literature. In the present paper, we prove that the family of such classes is infinite. Moreover, we show that the same is true with respect to linear clique-width.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||||
Journal or Publication Title: | Discrete Applied Mathematics | ||||||||
Publisher: | Elsevier Science Ltd. | ||||||||
ISSN: | 0166-218X | ||||||||
Official Date: | 30 October 2018 | ||||||||
Dates: |
|
||||||||
Volume: | 248 | ||||||||
Page Range: | pp. 145-152 | ||||||||
DOI: | 10.1016/j.dam.2017.02.012 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 21 February 2017 | ||||||||
Date of first compliant Open Access: | 23 March 2018 | ||||||||
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