On the complexity of colouring by superdigraphs of bipartite graphs
DOI10.1016/0012-365X(92)90276-LzbMATH Open0783.05047OpenAlexW2007374992MaRDI QIDQ686279FDOQ686279
Authors: Pavol Hell, Gary MacGillivray, Jørgen Bang-Jensen 
Publication date: 14 October 1993
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0012-365x(92)90276-l
Recommendations
Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Graph theory
- Title not available (Why is that?)
- On the complexity of H-coloring
- The complexity of satisfiability problems
- The complexity of theorem-proving procedures
- On multiplicative graphs and the product conjecture
- Color-families are dense
- Title not available (Why is that?)
- On classes of relations and graphs determined by subobjects and factorobjects
- Polynomial graph-colorings
- Contractibility and NP-completeness
- The Complexity of Colouring by Semicomplete Digraphs
- Hereditarily hard \(H\)-colouring problems
- The effect of two cycles on the complexity of colourings by directed graphs
- On the complexity of the general coloring problem
- Title not available (Why is that?)
- On unavoidable digraphs in orientations of graphs
- On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs
Cited In (14)
- Graph partitions with prescribed patterns
- Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy.
- Graph homomorphisms with infinite targets
- Logical Approaches to Computational Barriers
- Neighborhood hypergraphs of digraphs and some matrix permutation problems
- Colouring, constraint satisfaction, and complexity
- Homomorphisms to oriented cycles
- On the algebraic structure of combinatorial problems
- The effect of two cycles on the complexity of colourings by directed graphs
- The complexity of arc-colorings for directed hypergraphs
- Hereditarily hard \(H\)-colouring problems
- Complexity of tree homomorphisms
- The complexity of colouring symmetric relational systems
- Homomorphisms to oriented paths
This page was built for publication: On the complexity of colouring by superdigraphs of bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686279)
