Universality of intervals of line graph order

DOI10.1016/J.EJC.2014.04.008MaRDI QIDQ740276zbMATH OpenOpenAlexFDO

Authors Jiří Fiala, Jan Hubička, Yangjing Long

Publication date 2 September 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.3736

zbMATH Keywords

homomorphism order of line graphs of finite graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Graph operations (line graphs, products, etc.) (05C76)

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

Recommendations

• An universality argument for graph homomorphisms
• Fractal property of the graph homomorphism order
• On universal graphs for hom-properties
• Universal partial order represented by means of oriented trees and other simple graphs
• Density of universal classes of series-parallel graphs

Cites work

• scientific article; zbMATH DE number 3650785 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Color-families are dense
• Density of universal classes of series-parallel graphs
• Finite common coverings of graphs
• Finite paths are universal
• Finite presentation of homogeneous graphs, posets and Ramsey classes
• Graph minors. XX: Wagner's conjecture
• Labeled posets are universal
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Mathematical Foundations of Computer Science 2005
• Minimal universal and dense minor closed classes
• Minors of Boolean functions with respect to clique functions and hypergraph homomorphisms
• On the homomorphism order of labeled posets
• On universal partly ordered sets and classes
• Path homomorphisms
• Some examples of universal and generic partial orders
• Universal Infinite Partially Ordered Sets
• Universal partial order represented by means of oriented trees and other simple graphs

Cited in

(5)

• Fractal property of the graph homomorphism order
• Universal partial order represented by means of oriented trees and other simple graphs
• Which line-graphs are perfectly orderable?
• On tension-continuous mappings
• An universality argument for graph homomorphisms

This page was built for publication: Universality of intervals of line graph order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q740276)