On the complexity of colouring by superdigraphs of bipartite graphs

DOI10.1016/0012-365X(92)90276-LzbMath0783.05047OpenAlexW2007374992MaRDI QIDQ686279

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 graphdigraphcolouringhomomorphismNP-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items

Graph homomorphisms with infinite targets ⋮ Homomorphisms to oriented paths ⋮ Complexity of tree homomorphisms ⋮ The effect of two cycles on the complexity of colourings by directed graphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Graph partitions with prescribed patterns ⋮ On the algebraic structure of combinatorial problems ⋮ Hereditarily hard \(H\)-colouring problems ⋮ Homomorphisms to oriented cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Color-families are dense
• Polynomial graph-colorings
• On classes of relations and graphs determined by subobjects and factorobjects
• Hereditarily hard \(H\)-colouring problems
• Contractibility and NP-completeness
• On unavoidable digraphs in orientations of 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 complexity of satisfiability problems
• The complexity of theorem-proving procedures