Show simple item record

dc.contributor.authorKorpelainen, Nicholas
dc.contributor.authorAtminas, Aistis
dc.contributor.authorBrignall, Robert
dc.contributor.authorVatter, Vincent
dc.contributor.authorLozin, Vadim
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.
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
refterms.dateFOA2019-02-28T15:02:48Z
html.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.


Files in this item

Thumbnail
Name:
Korpelainen_2015_Well-quasi-or ...
Size:
273.7Kb
Format:
PDF
Description:
Published PDF

This item appears in the following Collection(s)

Show simple item record

http://creativecommons.org/licenses/by/4.0/
Except where otherwise noted, this item's license is described as http://creativecommons.org/licenses/by/4.0/