Universal partial order represented by means of oriented trees and other simple graphs

DOI10.1016/j.ejc.2004.01.008zbMath1060.05092OpenAlexW2078093849MaRDI QIDQ1775038

Jaroslav Nešetřil, Jan Hubička

Publication date: 4 May 2005

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

Full work available at URL: https://doi.org/10.1016/j.ejc.2004.01.008

zbMATH Keywords

representationsautomorphismsuniversalitypartially ordered setsgraph homomorphismsoriented treescubic planar graphs

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items (18)

An universality argument for graph homomorphisms ⋮ Minimal universal and dense minor closed classes ⋮ Order-couniversality of the complete infinitary tree: an application of zero-divisor graphs ⋮ Fractal property of the graph homomorphism order ⋮ No finite-infinite antichain duality in the homomorphism poset of directed graphs ⋮ Towards a characterization of universal categories ⋮ Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities ⋮ On the homomorphism order of labeled posets ⋮ Unnamed Item ⋮ A finite presentation of the rational Urysohn space ⋮ Labeled posets are universal ⋮ Tree-depth, subgraph coloring and homomorphism bounds ⋮ Minors of Boolean functions with respect to clique functions and hypergraph homomorphisms ⋮ The homomorphism lattice induced by a finite algebra ⋮ Universality of intervals of line graph order ⋮ Finite paths are universal ⋮ Finite dualities and map-critical graphs on a fixed surface ⋮ A surprising permanence of old motivations (a not-so-rigid story)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Theory of relations. Transl. from the French by P. Clote
• Endomorphism monoids and topological subgraphs of graphs
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Aspects of structural combinatorics. (Graph homomorphisms and their use)
• Automorphism groups of graphs and edge-contraction
• On universal partly ordered sets and classes
• Homomorphisms of graphs into odd cycles
• Universal Infinite Partially Ordered Sets
• Universal relational systems
• Duality and Polynomial Testing of Tree Homomorphisms
• Path homomorphisms
• Groups and Monoids of Regular Graphs (And of Graphs with Bounded Degrees)
• The random graph
• Finite paths are universal

This page was built for publication: Universal partial order represented by means of oriented trees and other simple graphs