Well-quasi-order for permutation graphs omitting a path and a clique

Journal article


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.
AuthorsKorpelainen, Nicholas, Atminas, Aistis, Brignall, Robert, Vatter, Vincent and Lozin, Vadim
Abstract

We consider well-quasi-order for classes of permutation graphs which omit both a path and a clique. Our principle result is that the class of permutation graphs omitting P5 and a clique of any size is well-quasi-ordered. This is proved by giving a structural decomposition of the corresponding permutations. We also exhibit three infinite antichains to show that the classes of permutation graphs omitting {P6,K6}, {P7,K5}, and {P8,K4} are not well-quasi-ordered.

KeywordsGraph theory; Permutation patterns; Well-quasi-ordering; Graphs
Year2015
JournalThe Electronic Journal of Combinatorics
PublisherAustralian National University
ISSN1077-8926
Web address (URL)http://hdl.handle.net/10545/621049
http://creativecommons.org/licenses/by/4.0/
hdl:10545/621049
Publication dates29 Apr 2015
Publication process dates
Deposited23 Nov 2016, 15:21
ContributorsUniversity of Derby
File
File Access Level
Open
File
File Access Level
Open
File
File Access Level
Open
Permalink -

https://repository.derby.ac.uk/item/94411/well-quasi-order-for-permutation-graphs-omitting-a-path-and-a-clique

Download files

  • 13
    total views
  • 8
    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
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
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