The effect of two cycles on the complexity of colourings by directed graphs
From MaRDI portal
Publication:911612
DOI10.1016/0166-218X(90)90017-7zbMath0697.05029OpenAlexW2021465457MaRDI QIDQ911612
Jörgen Bang-Jensen, Pavol Hell
Publication date: 1990
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(90)90017-7
Related Items
The complexity of colouring symmetric relational systems, Graph homomorphisms with infinite targets, Homomorphisms to oriented paths, Colorings and girth of oriented planar graphs, Towards a dichotomy theorem for the counting constraint satisfaction problem, Complexity of tree homomorphisms, List homomorphisms to reflexive graphs, Homomorphisms and oriented colorings of equivalence classes of oriented graphs, Colouring, constraint satisfaction, and complexity, Path homomorphisms, Minimum cost homomorphisms to semicomplete multipartite digraphs, On the complexity of colouring by superdigraphs of bipartite graphs, The core of a graph, Rigid binary relations on a 4-element domain, The complexity of tropical graph homomorphisms, The complexity of colouring by locally semicomplete digraphs, The \(C_{k}\)-extended graft construction, Graph partitions with prescribed patterns, Testing subgraphs in directed graphs, CSP dichotomy for special triads, The recognition of bound quivers using edge-coloured homomorphisms, Hereditarily hard \(H\)-colouring problems, Homomorphisms to oriented cycles
Cites Work
- Unnamed Item
- Unnamed Item
- On the complexity of colouring by superdigraphs of bipartite graphs
- On multiplicative graphs and the product conjecture
- On classes of relations and graphs determined by subobjects and factorobjects
- Hereditarily hard \(H\)-colouring problems
- On unavoidable digraphs in orientations of graphs
- The Complexity of Colouring by Semicomplete Digraphs
- On the complexity of the general coloring problem
