Homomorphisms to oriented paths
From MaRDI portal
Publication:1336655
DOI10.1016/0012-365X(94)90235-6zbMath0819.05030MaRDI QIDQ1336655
Publication date: 27 August 1995
Published in: Discrete Mathematics (Search for Journal in Brave)
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