Well-quasi-order for permutation graphs omitting a path and a clique (Q2344822): Difference between revisions
From MaRDI portal
Latest revision as of 02:55, 10 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Well-quasi-order for permutation graphs omitting a path and a clique |
scientific article |
Statements
Well-quasi-order for permutation graphs omitting a path and a clique (English)
0 references
18 May 2015
0 references
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.
0 references
well-quasi-order
0 references
permutation graphs
0 references
permutations
0 references
graphs
0 references