A new graph construction of unbounded clique-width.

Journal article


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
AuthorsKorpelainen, Nicholas
Abstract

We define permutation-partition graphs by replacing one part of a 2K2-free bipartite graph (a bipartite chain graph) by an induced linear forest. We show that this hereditary graph class is of of unbounded clique-width (with a new graph construction of large clique-width). We show that this graph class contains no minimal graph class of unbounded clique-width, and give a conjecture for a contained boundary class for this property.

KeywordsClique-width; Hereditary class; Graph theory
Year2016
JournalElectronic Notes in Discrete Mathematics
PublisherElsevier
ISSN15710653
Digital Object Identifier (DOI)https://doi.org/10.1016/j.endm.2016.11.005
Web address (URL)http://hdl.handle.net/10545/622379
http://creativecommons.org/licenses/by-nc-nd/4.0/
hdl:10545/622379
Publication dates01 Dec 2016
Publication process dates
Deposited19 Mar 2018, 13:15
Rights

Archived with thanks to Electronic Notes in Discrete Mathematics

ContributorsUniversity of Derby
File
File Access Level
Open
File
File Access Level
Open
Permalink -

https://repository.derby.ac.uk/item/93z36/a-new-graph-construction-of-unbounded-clique-width

Download files

  • 17
    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
Infinitely many minimal classes of graphs of unbounded clique-width.
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
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