English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

This paper is a contribution to the study of hereditary classes of relationalstructures, these classes being quasi-ordered by embeddability. It deals withthe specific case of ordered sets of width two and the corresponding bichainsand incomparability graphs.  Several open problems about hereditary classes of relational structures whichhave been considered over the years have positive answer in this case. Forexample, well-quasi-ordered hereditary classes of finite bipartite permutationgraphs, respectively finite 321-avoiding permutations, have been characterizedby Korpelainen, Lozin and Mayhill, respectively by Albert, Brignall, Ru\v{s}kucand Vatter.  We provide another proof of the results mentioned above. It is based on theexistence of a countable universal poset of width two, obtained by the firstauthor in 1978, his notion of multichainability (1978) (a kind of analog toletter-graphs), and metric properties of incomparability graphs. Using Laver'stheorem (1971) on better-quasi-ordering (bqo) of countable chains we prove thata wqo hereditary class of finite or countable bipartite permutation graphs isnecessarily bqo. This gives a positive answer to a conjecture of Nash-Williams(1965) in this case. We extend a previous result of Albert et al. by provingthat if a hereditary class of finite, respectively countable, bipartitepermutation graphs is wqo, respectively bqo, then the corresponding hereditaryclasses of posets of width at most two and bichains are wqo, respectively bqo.  Several notions of labelled wqo are also considered. We prove that they areall equivalent in the case of bipartite permutation graphs, posets of width atmost two and the corresponding bichains. We characterize hereditary classes offinite bipartite permutation graphs which remain wqo when labels from a wqo areadded.

Hereditary classes of ordered sets of width at most two