Well-quasi-order for permutation graphs omitting a path and a clique (Q2344822)

Summary: 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.