Linear clique-width for hereditary classes of cographs

Journal article

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
AuthorsBrignall, Robert, Korpelainen, Nicholas and Vatter, Vincent
Abstract

The class of cographs is known to have unbounded linear clique-width. We prove that a hereditary class of cographs has bounded linear clique-width if and only if it does not contain all quasi-threshold graphs or their complements. The proof borrows ideas from the enumeration of permutation classes.

KeywordsCograph; Graph theory; Clique-width; Graph class
Year2016
JournalJournal of Graph Theory
PublisherWiley
ISSN0364-9024
Digital Object Identifier (DOI)https://doi.org/10.1002/jgt.22037
Web address (URL)http://hdl.handle.net/10545/621048
http://creativecommons.org/licenses/by/4.0/
hdl:10545/621048
Publication dates28 Mar 2016
Publication process dates
Deposited23 Nov 2016, 15:08
Rights

Archived with thanks to Journal of Graph Theory

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

https://repository.derby.ac.uk/item/93899/linear-clique-width-for-hereditary-classes-of-cographs

Log in to edit

Download files

  • 19
    total views
  • 0
    total downloads
  • 1
    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
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.