Well-quasi-order for permutation graphs omitting a path and a clique
Journal article
Korpelainen, Nicholas, Atminas, Aistis, Brignall, Robert, Vatter, Vincent and Lozin, Vadim 2015. Well-quasi-order for permutation graphs omitting a path and a clique. The Electronic Journal of Combinatorics.
| Authors | Korpelainen, Nicholas, Atminas, Aistis, Brignall, Robert, Vatter, Vincent and Lozin, Vadim |
|---|---|
| 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 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. |
| Keywords | Graph theory; Permutation patterns; Well-quasi-ordering; Graphs |
| Year | 2015 |
| Journal | The Electronic Journal of Combinatorics |
| Publisher | Australian National University |
| ISSN | 1077-8926 |
| Web address (URL) | http://hdl.handle.net/10545/621049 |
| http://creativecommons.org/licenses/by/4.0/ | |
| hdl:10545/621049 | |
| Publication dates | 29 Apr 2015 |
| Publication process dates | |
| Deposited | 23 Nov 2016, 15:21 |
| Contributors | University of Derby |
| File | File Access Level Open |
| File | File Access Level Open |
| File | File Access Level Open |
Permalink -
https://repository.derby.ac.uk/item/94411/well-quasi-order-for-permutation-graphs-omitting-a-path-and-a-clique
Download files
27
total views16
total downloads0
views this month1
downloads this month
Export as
Related outputs
A boundary class for the k-path partition problem.
Korpelainen, Nicholas 2018. A boundary class for the k-path partition problem. Electronic Notes in Discrete Mathematics. https://doi.org/10.1016/j.endm.2018.05.009
A new graph construction of unbounded clique-width.
Korpelainen, Nicholas 2016. A new graph construction of unbounded clique-width. Electronic Notes in Discrete Mathematics. https://doi.org/10.1016/j.endm.2016.11.005Infinitely many minimal classes of graphs of unbounded clique-width.
Collins, Andrew, Foniok, Jan, Korpelainen, Nicholas, Lozin, Vadim and Zamaraev, Viktor 2017. Infinitely many minimal classes of graphs of unbounded clique-width. Discrete Applied Mathematics. https://doi.org/10.1016/j.dam.2017.02.012