Path homomorphisms

DOI10.1017/S0305004100074806MaRDI QIDQ4892428zbMATH OpenOpenAlexWikidataFDO

Authors J. Nešetřil, Xuding Zhu

Publication date 6 March 1997

Published in Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0305004100074806

zbMATH Keywords

countable posethomomorphismpathstrees

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph theory (05C99) Combinatorics of partially ordered sets (06A07)

Recommendations

• Finite paths are universal
• Finite paths are universal
• Homomorphisms to oriented paths
• The number of path homomorphisms by the generalized Catalan number
• On the homomorphism order of labeled posets

Cites work

• Homomorphisms of graphs and of their orientations
• Homomorphisms to oriented cycles
• Homomorphisms to oriented paths
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• Images of rigid digraphs
• Mutiplicativity of oriented cycles
• On classes of relations and graphs determined by subobjects and factorobjects
• On multiplicative graphs and the product conjecture
• On the complexity of H-coloring
• On the complexity of the general coloring problem
• On unavoidable digraphs in orientations of graphs
• Ordering by Divisibility in Abstract Algebras
• Polynomial graph-colorings
• Symmetric graphs and interpretations
• The Complexity of Colouring by Semicomplete Digraphs
• The core of a graph
• The effect of two cycles on the complexity of colourings by directed graphs
• Universality of \(A\)-mote graphs

Cited in

(17)

• A surprising permanence of old motivations (a not-so-rigid story)
• An algorithm for the number of path homomorphisms
• Fractional multiples of graphs and the density of vertex-transitive graphs
• Homomorphic preimages of geometric paths
• Universal partial order represented by means of oriented trees and other simple graphs
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• The homomorphism poset of \(K_{2,n}\)
• Circular colouring and graph homomorphism
• scientific article; zbMATH DE number 1512759 (Why is no real title available?)
• Finite paths are universal
• Finite paths are universal
• Density and fractal property of the class of oriented trees
• Universality of intervals of line graph order
• Paths algebra, similarities and system decomposition
• Finite presentation of homogeneous graphs, posets and Ramsey classes
• Minimal universal and dense minor closed classes

This page was built for publication: Path homomorphisms

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