On the Homomorphism Order of Oriented Paths and Trees

Abstrakt

A partial order is universal if it contains every countable partial order as a suborder. In 2017, Fiala, Hubička, Long and Nešetřil showed that every interval in the homomorphism order of graphs is universal, with the only exception being the trivial gap [K1,K2].

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.

Klíčová slova

• Homomorphism
• Order
• Oriented Paths
• Trees