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

Aistis Atminas, Robert Brignall, Nicholas Korpelainen, Vadim Lozin, Vincent Vatter

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)1-21
Number of pages21
JournalElectronic Journal of Combinatorics
Issue number2
Publication statusPublished - 29 Apr 2015
Externally publishedYes


  • Automatic sequence
  • Central limit theorem
  • Fourier coefficient
  • Non-differentiability
  • Periodic fluctuation
  • Transducer

Cite this