• Well-quasi-order for permutation graphs omitting a path and a clique

      Korpelainen, Nicholas; Atminas, Aistis; Brignall, Robert; Vatter, Vincent; Lozin, Vadim; University of Derby (Australian National University, 2015-04-29)
      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 P5 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 {P6,K6}, {P7,K5}, and {P8,K4} are not well-quasi-ordered.