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 $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.

Viewing alternatives

Look up in Google Scholar

Download history

Item Actions

Export

About

CORE (COnnecting REpositories)