Geodesic
Well-quasi-order for permutation graphs omitting a path and a clique
Aistis Atminas1 ; Robert Brignall2 ; Nicholas Korpelainen3 ; Vadim Lozin1 ; Vincent Vatter4
1University of Warwick, UK
2The Open University, UK
3University of Derby, UK
4University of Florida, USA
The electronic journal of combinatorics, Tome 22 (2015) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/4074
Classification : 05C75, 05A05, 05A15, 05C38, 05C69
Mots-clés : well-quasi-order, permutation graphs, permutations, graphs

Aistis Atminas  1   ; Robert Brignall  2   ; Nicholas Korpelainen  3   ; Vadim Lozin  1   ; Vincent Vatter  4

1 University of Warwick, UK
2 The Open University, UK
3 University of Derby, UK
4 University of Florida, USA 
@article{10_37236_4074,
     author = {Aistis Atminas and Robert Brignall and Nicholas Korpelainen and Vadim Lozin and Vincent Vatter},
     title = {Well-quasi-order for permutation graphs omitting a path and a clique},
     journal = {The electronic journal of combinatorics},
     year = {2015},
     volume = {22},
     number = {2},
     doi = {10.37236/4074},
     zbl = {1312.05114},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4074/}
}
TY  - JOUR
AU  - Aistis Atminas
AU  - Robert Brignall
AU  - Nicholas Korpelainen
AU  - Vadim Lozin
AU  - Vincent Vatter
TI  - Well-quasi-order for permutation graphs omitting a path and a clique
JO  - The electronic journal of combinatorics
PY  - 2015
VL  - 22
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4074/
DO  - 10.37236/4074
ID  - 10_37236_4074
ER  - 
%0 Journal Article
%A Aistis Atminas
%A Robert Brignall
%A Nicholas Korpelainen
%A Vadim Lozin
%A Vincent Vatter
%T Well-quasi-order for permutation graphs omitting a path and a clique
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/4074/
%R 10.37236/4074
%F 10_37236_4074
Aistis Atminas; Robert Brignall; Nicholas Korpelainen; Vadim Lozin; Vincent Vatter. Well-quasi-order for permutation graphs omitting a path and a clique. The electronic journal of combinatorics, Tome 22 (2015) no. 2. doi: 10.37236/4074

Cité par Sources :