Well-quasi-order for permutation graphs omitting a path and a clique

Aistis Atminas; Robert Brignall; Nicholas Korpelainen; Vadim Lozin; Vincent Vatter

doi:10.37236/4074

Well-quasi-order for permutation graphs omitting a path and a clique

Aistis Atminas, Robert Brignall, Nicholas Korpelainen, Vadim Lozin, Vincent Vatter

Research output: Contribution to journal › Article › peer-review

4 Citations (Scopus)

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

Original language	English
Pages (from-to)	1-21
Number of pages	21
Journal	Electronic Journal of Combinatorics
Volume	22
Issue number	2
DOIs	https://doi.org/10.37236/4074
Publication status	Published - 29 Apr 2015
Externally published	Yes

Keywords

Automatic sequence
Central limit theorem
Fourier coefficient
Non-differentiability
Periodic fluctuation
Transducer

Access to Document

10.37236/4074

Cite this

@article{f6f46760ef0d4065b602f0d26e91028f,

title = "Well-quasi-order for permutation graphs omitting a path and a clique",

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 = "Automatic sequence, Central limit theorem, Fourier coefficient, Non-differentiability, Periodic fluctuation, Transducer",

author = "Aistis Atminas and Robert Brignall and Nicholas Korpelainen and Vadim Lozin and Vincent Vatter",

year = "2015",

month = apr,

day = "29",

doi = "10.37236/4074",

language = "English",

volume = "22",

pages = "1--21",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

number = "2",

}

TY - JOUR

T1 - Well-quasi-order for permutation graphs omitting a path and a clique

AU - Atminas, Aistis

AU - Brignall, Robert

AU - Korpelainen, Nicholas

AU - Lozin, Vadim

AU - Vatter, Vincent

PY - 2015/4/29

Y1 - 2015/4/29

N2 - 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.

AB - 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.

KW - Automatic sequence

KW - Central limit theorem

KW - Fourier coefficient

KW - Non-differentiability

KW - Periodic fluctuation

KW - Transducer

UR - http://www.scopus.com/inward/record.url?scp=84928688068&partnerID=8YFLogxK

U2 - 10.37236/4074

DO - 10.37236/4074

M3 - Article

AN - SCOPUS:84928688068

SN - 1077-8926

VL - 22

SP - 1

EP - 21

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 2

ER -

Well-quasi-order for permutation graphs omitting a path and a clique

Abstract

Keywords

Access to Document

Other files and links

Cite this