Copy the page URI to the clipboard
Atminas, Aistis; Brignall, Robert; Korpelainen, Nicholas; Lozin, Vadim and Vatter, Vincent
(2015).
URL: http://www.combinatorics.org/ojs/index.php/eljc/ar...
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 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
,
, and
are not well-quasi-ordered.
Viewing alternatives
Download history
Item Actions
Export
About
- Item ORO ID
- 42612
- Item Type
- Journal Item
- ISSN
- 1077-8926
- Project Funding Details
-
Funded Project Name Project ID Funding Body Infinite Antichains of Combinatorial Structures EP/J006130/1 EPSRC - Extra Information
- 21 pp.
- Keywords
- well-quasi-order; permutation graphs; permutations; graphs
- Academic Unit or School
-
Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM) - Copyright Holders
- © 2015 The Authors
- Related URLs
- Depositing User
- Robert Brignall