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
published in: European journal of combinatorics, 41 (2014), p. 221-231
DOI number (of the published article): 10.1016/j.ejc.2014.04.008
Download full preprint: PDF (390 kB)
We prove that for every d ≥ 3 the homomorphism order of the class of line graphs of ﬁnite graphs with maximal degree d is universal. This means that every ﬁnite or countably inﬁnite partially ordered set may be represented by line graphs of graphs with maximal degree d ordered by the existence of a homomorphism.