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.

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

Item Actions

Export

You can export this page using these formats

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
• • http://www.combinatorics.org/ojs/index.p...(Other)
• Depositing User
• Robert Brignall