Hdl Handle:
http://hdl.handle.net/10545/621049
Title:
Well-quasi-order for permutation graphs omitting a path and a clique
Authors:
Korpelainen, Nicholas ( 0000-0001-7142-9515 ) ; Atminas, Aistis; Brignall, Robert; Vatter, Vincent; 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.
Affiliation:
University of Derby
Citation:
Korpelainen, N. et al (2015) 'Well-quasi-order for permutation graphs omitting a path and a clique', The Electronic Journal of Combinatorics, 22 (2) #P2.20
Publisher:
Australian National University
Journal:
The Electronic Journal of Combinatorics
Issue Date:
29-Apr-2015
URI:
http://hdl.handle.net/10545/621049
Additional Links:
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p20
Type:
Article
Language:
en
ISSN:
1077-8926
Appears in Collections:
Department of Electronics, Computing & Maths

Full metadata record

DC FieldValue Language
dc.contributor.authorKorpelainen, Nicholasen
dc.contributor.authorAtminas, Aistisen
dc.contributor.authorBrignall, Roberten
dc.contributor.authorVatter, Vincenten
dc.contributor.authorLozin, Vadimen
dc.date.accessioned2016-11-23T15:21:10Z-
dc.date.available2016-11-23T15:21:10Z-
dc.date.issued2015-04-29-
dc.identifier.citationKorpelainen, N. et al (2015) 'Well-quasi-order for permutation graphs omitting a path and a clique', The Electronic Journal of Combinatorics, 22 (2) #P2.20en
dc.identifier.issn1077-8926-
dc.identifier.urihttp://hdl.handle.net/10545/621049-
dc.description.abstractWe 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.en
dc.language.isoenen
dc.publisherAustralian National Universityen
dc.relation.urlhttp://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i2p20en
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/en
dc.subjectGraph theoryen
dc.subjectPermutation patternsen
dc.subjectWell-quasi-orderingen
dc.subjectGraphsen
dc.titleWell-quasi-order for permutation graphs omitting a path and a cliqueen
dc.typeArticleen
dc.contributor.departmentUniversity of Derbyen
dc.identifier.journalThe Electronic Journal of Combinatoricsen
This item is licensed under a Creative Commons License
Creative Commons
All Items in UDORA are protected by copyright, with all rights reserved, unless otherwise indicated.