arXiv Open Access 2022

On the Homomorphism Order of Oriented Paths and Trees

Jan Hubička Jaroslav Nešetřil Pablo Oviedo Oriol Serra

Lihat Sumber

Abstrak

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 $[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.

Topik & Kata Kunci

math.CO cs.DM

Penulis (4)

Jan Hubička

Jaroslav Nešetřil

Pablo Oviedo

Oriol Serra

Format Sitasi

APA MLA BibTeX

Hubička, J., Nešetřil, J., Oviedo, P., Serra, O. (2022). On the Homomorphism Order of Oriented Paths and Trees. https://arxiv.org/abs/2201.09365

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2022
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓