The complexity of colouring by locally semicomplete digraphs

DOI10.1016/J.DISC.2010.03.033zbMath1221.05173OpenAlexW2036553843MaRDI QIDQ709314

Jacobus Swarts, Gary MacGillivray, Jörgen Bang-Jensen

Publication date: 18 October 2010

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2010.03.033

zbMATH Keywords

complexityNP-completenesspolynomial algorithmlocally semicomplete digraphsdigraph homomorphism

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Colourings, homomorphisms, and partitions of transitive digraphs ⋮ The \(C_{k}\)-extended graft construction ⋮ Dichotomy for finite tournaments of mixed-type

Cites Work

• 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
• Polynomial graph-colorings
• Locally semicomplete digraphs: A generalization of tournaments
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Complexity of Colouring by Semicomplete Digraphs
• On homomorphisms to acyclic local tournaments
• Digraphs

This page was built for publication: The complexity of colouring by locally semicomplete digraphs