Homomorphisms to oriented paths

DOI10.1016/0012-365X(94)90235-6zbMath0819.05030MaRDI QIDQ1336655

Xuding Zhu, Pavol Hell

Publication date: 27 August 1995

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items

ILP formulation of the degree-constrained minimum spanning hierarchy problem, Complexity of tree homomorphisms, Semidefinite programming and its applications to NP problems, Homomorphic preimages of geometric paths, Interleaved adjoints of directed graphs, Path homomorphisms, Learning logic programs with structured background knowledge, Graph partitions with prescribed patterns, A surprising permanence of old motivations (a not-so-rigid story), Hereditarily hard \(H\)-colouring problems, Dualities for Constraint Satisfaction Problems, Homomorphisms to oriented cycles

Cites Work

• Unnamed Item
• On the complexity of colouring by superdigraphs of bipartite graphs
• Symmetric graphs and interpretations
• The effect of two cycles on the complexity of colourings by directed graphs
• On the complexity of H-coloring
• On multiplicative graphs and the product conjecture
• Polynomial graph-colorings
• On classes of relations and graphs determined by subobjects and factorobjects
• Homomorphisms to oriented cycles
• Hereditarily hard \(H\)-colouring problems
• Some new good characterizations for directed graphs
• The Complexity of Colouring by Semicomplete Digraphs
• On the complexity of the general coloring problem
• On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs
• The Existence of Homomorphisms to Oriented Cycles