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

zbMATH Keywords

complexitybipartite graphcolouringdigraphhomomorphismNP-complete

Mathematics Subject Classification ID

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)

Recommendations

• The Complexity of Colouring by Semicomplete Digraphs
• Hereditarily hard \(H\)-colouring problems
• On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs
• The effect of two cycles on the complexity of colourings by directed graphs
• scientific article; zbMATH DE number 866665

Cites Work

• scientific article; zbMATH DE number 4008417 (Why is no real title available?)
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Color-families are dense
• Contractibility and NP-completeness
• Graph theory
• Hereditarily hard \(H\)-colouring problems
• 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 the general coloring problem
• On unavoidable digraphs in orientations of graphs
• Polynomial graph-colorings
• The Complexity of Colouring by Semicomplete Digraphs
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• The effect of two cycles on the complexity of colourings by directed graphs

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)