Well-Quasi-Order for Permutation Graphs Omitting a Path and a Clique
| Autor: | Atminas, Aistis, Brignall, Robert, Korpelainen, Nicholas, Lozin, Vadim, Vatter, Vincent |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 21 pages, 9 figures, to appear in Elec. J. Comb |
| Databáze: | arXiv |
| Externí odkaz: |
|