Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique

2013/12/20 by Aistis Atminas, Robert Brignall, Atminas, Aistis +7
Mathematics · #05A05 #05C75 (secondary) #06A07 (primary) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A05 #msc:05C75 #msc:06A07

paper · pdf · doi:10.48550/arxiv.1312.5907

21 pages, 9 figures, to appear in Elec. J. Comb

arxiv created 2015/04/27 · arxiv updated 2015/04/28

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₅ 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₆,K₆\, \P₇,K₅\, and \P₈,K₄\ are not well-quasi-ordered.

Related

• Labelled well-quasi-order for permutation classes
• A counterexample regarding labelled well-quasi-ordering
• Bipartite Induced Subgraphs and Well-Quasi-Ordering
• Well-quasi-ordered classes of bounded clique-width
• Well-quasi-ordering does not imply bounded clique-width