Universality of intervals of line graph order

Jiri Fiala, Jan Hubicka, and Yangjing Long

Contact the author: Please use for correspondence this email.
Submission date: 24. Feb. 2014
Pages: 14
published in: European journal of combinatorics, 41 (2014), p. 221-231 
DOI number (of the published article): 10.1016/j.ejc.2014.04.008
Bibtex
Download full preprint: PDF (390 kB)

Abstract:
We prove that for every d ≥ 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.