Universality of intervals of line graph order

Abstract

We prove that for every $d\ge 3$ the homomorphism order of the class of line graphs of finite graphs with maximal degree $d$ is universal. This means that every finite or countably infinite partially ordered set may be represented by line graphs of graphs with maximal degree $d$ ordered by the existence of a homomorphism.

13 pages, 8 figures, accepted to European Journal of Combinatorics

References in corpus (1)

• On the homomorphism order of labeled posets