Infinitely many minimal classes of graphs of unbounded clique-width.

Journal article


Collins, Andrew, Foniok, Jan, Korpelainen, Nicholas, Lozin, Vadim and Zamaraev, Viktor 2017. Infinitely many minimal classes of graphs of unbounded clique-width. Discrete Applied Mathematics. https://doi.org/10.1016/j.dam.2017.02.012
AuthorsCollins, Andrew, Foniok, Jan, Korpelainen, Nicholas, Lozin, Vadim and Zamaraev, Viktor
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.

KeywordsClique-width; Hereditary class; Graph theory
Year2017
JournalDiscrete Applied Mathematics
PublisherElsevier
ISSN0166218X
Digital Object Identifier (DOI)https://doi.org/10.1016/j.dam.2017.02.012
Web address (URL)http://hdl.handle.net/10545/622378
http://creativecommons.org/licenses/by-nc-nd/4.0/
hdl:10545/622378
Publication dates23 Mar 2017
Publication process dates
Deposited19 Mar 2018, 13:13
Accepted13 Feb 2017
Rights

Archived with thanks to Discrete Applied Mathematics

ContributorsUniversity of Warwick, Manchester Metropolitan University and University of Derby
File
File Access Level
Open
File
File Access Level
Open
Permalink -

https://repository.derby.ac.uk/item/93ww7/infinitely-many-minimal-classes-of-graphs-of-unbounded-clique-width

Download files

  • 12
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as

Related outputs

A boundary class for the k-path partition problem.
Korpelainen, Nicholas 2018. A boundary class for the k-path partition problem. Electronic Notes in Discrete Mathematics. https://doi.org/10.1016/j.endm.2018.05.009
A new graph construction of unbounded clique-width.
Korpelainen, Nicholas 2016. A new graph construction of unbounded clique-width. Electronic Notes in Discrete Mathematics. https://doi.org/10.1016/j.endm.2016.11.005
Well-quasi-order for permutation graphs omitting a path and a clique
Korpelainen, Nicholas, Atminas, Aistis, Brignall, Robert, Vatter, Vincent and Lozin, Vadim 2015. Well-quasi-order for permutation graphs omitting a path and a clique. The Electronic Journal of Combinatorics.
Linear clique-width for hereditary classes of cographs
Brignall, Robert, Korpelainen, Nicholas and Vatter, Vincent 2016. Linear clique-width for hereditary classes of cographs. Journal of Graph Theory. https://doi.org/10.1002/jgt.22037