The Open UniversitySkip to content
 

Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique

Atminas, Aistis; Brignall, Robert; Korpelainen, Nicholas; Lozin, Vadim and Vatter, Vincent (2015). Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique. Electronic Journal of Combinatorics, 22(2), article no. P2.20.

Full text available as:
[img]
Preview
PDF (Version of Record) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (264kB) | Preview
URL: http://www.combinatorics.org/ojs/index.php/eljc/ar...
Google Scholar: Look up in Google Scholar

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 $P_5$ 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 $\{P_6,K_6\}$, $\{P_7,K_5\}$, and $\{P_8,K_4\}$ are not well-quasi-ordered.

Item Type: Journal Item
Copyright Holders: 2015 The Authors
ISSN: 1077-8926
Project Funding Details:
Funded Project NameProject IDFunding Body
Infinite Antichains of Combinatorial StructuresEP/J006130/1EPSRC
Extra Information: 21 pp.
Keywords: well-quasi-order; permutation graphs; permutations; graphs
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Related URLs:
Item ID: 42612
Depositing User: Robert Brignall
Date Deposited: 29 Apr 2015 14:29
Last Modified: 12 Dec 2018 06:00
URI: http://oro.open.ac.uk/id/eprint/42612
Share this page:

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU