On the complexity of colouring by superdigraphs of bipartite graphs

DOI10.1016/0012-365X(92)90276-LMaRDI QIDQ686279zbMATH OpenOpenAlexFDO

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)

• Hereditarily hard \(H\)-colouring problems
• Greedy algorithms, \(H\)-colourings and a complexity-theoretic dichotomy.
• The effect of two cycles on the complexity of colourings by directed graphs
• Graph homomorphisms with infinite targets
• Homomorphisms to oriented cycles
• Logical Approaches to Computational Barriers
• Graph partitions with prescribed patterns
• Colouring, constraint satisfaction, and complexity
• Complexity of tree homomorphisms
• Neighborhood hypergraphs of digraphs and some matrix permutation problems
• Homomorphisms to oriented paths
• The complexity of arc-colorings for directed hypergraphs
• The complexity of colouring symmetric relational systems
• On the algebraic structure of combinatorial problems

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)