Homomorphisms to oriented paths

DOI10.1016/0012-365X(94)90235-6MaRDI QIDQ1336655zbMATH OpenFDO

Authors Xuding Zhu, Pavol Hell

Publication date 27 August 1995

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

characterizationdigraphhomomorphismpolynomial algorithmoriented path\(H\)-colouringstree-duality

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Structural characterization of families of graphs (05C75)

Recommendations

• A Polynomial Algorithm for Homomorphisms to Oriented Cycles
• scientific article; zbMATH DE number 878894
• Complexity of tree homomorphisms
• The Existence of Homomorphisms to Oriented Cycles
• Duality pairs and homomorphisms to oriented and unoriented cycles
• A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
• Publication:4863467
• An algorithm for the number of path homomorphisms
• The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
• Directed path graph isomorphism

Cites work

• scientific article; zbMATH DE number 3520447 (Why is no real title available?)
• Hereditarily hard \(H\)-colouring problems
• Homomorphisms to oriented cycles
• On classes of relations and graphs determined by subobjects and factorobjects
• On multiplicative graphs and the product conjecture
• On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs
• On the complexity of H-coloring
• On the complexity of colouring by superdigraphs of bipartite graphs
• On the complexity of the general coloring problem
• Polynomial graph-colorings
• Some new good characterizations for directed graphs
• Symmetric graphs and interpretations
• The Complexity of Colouring by Semicomplete Digraphs
• The Existence of Homomorphisms to Oriented Cycles
• The effect of two cycles on the complexity of colourings by directed graphs

Cited in

(23)

• Hereditarily hard \(H\)-colouring problems
• Interleaved adjoints of directed graphs
• Orienteering with one endomorphism
• A surprising permanence of old motivations (a not-so-rigid story)
• Homomorphisms to oriented cycles
• On homomorphisms to acyclic local tournaments
• ILP formulation of the degree-constrained minimum spanning hierarchy problem
• Duality pairs and homomorphisms to oriented and unoriented cycles
• scientific article; zbMATH DE number 841621 (Why is no real title available?)
• Graph partitions with prescribed patterns
• Semidefinite programming and its applications to NP problems
• A Polynomial Algorithm for Homomorphisms to Oriented Cycles
• Complexity of tree homomorphisms
• Homomorphisms of random paths
• Homomorphic preimages of geometric paths
• Homomorphically full oriented graphs
• Homomorphisms to powers of digraphs
• scientific article; zbMATH DE number 2061631 (Why is no real title available?)
• Adjoint functors and tree duality
• Homology of Spaces of Directed Paths in Euclidean Pattern Spaces
• Dualities for Constraint Satisfaction Problems
• Path homomorphisms
• Learning logic programs with structured background knowledge

This page was built for publication: Homomorphisms to oriented paths

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