pith. sign in

arxiv: 2201.09365 · v2 · pith:7L2NY2GQnew · submitted 2022-01-23 · 🧮 math.CO · cs.DM

On the Homomorphism Order of Oriented Paths and Trees

classification 🧮 math.CO cs.DM
keywords orientedorderpathstreeseveryhomomorphismuniversalclass
0
0 comments X
read the original abstract

A partial order is universal if it contains every countable partial order as a suborder. In 2017, Fiala, Hubi\v{c}ka, Long and Ne\v{s}et\v{r}il showed that every interval in the homomorphism order of graphs is universal, with the only exception being the trivial gap $[K_1,K_2]$. We consider the homomorphism order restricted to the class of oriented paths and trees. We show that every interval between two oriented paths or oriented trees of height at least 4 is universal. The exceptional intervals coincide for oriented paths and trees and are contained in the class of oriented paths of height at most 3, which forms a chain.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.