The complexity of colouring by locally semicomplete digraphs
type: Item
instance of: scholarly article
title: The complexity of colouring by locally semicomplete digraphs
zbMATH Open document ID: 1221.05173
author: Gary MacGillivray
author: Jacobus Swarts
author: Jørgen Bang-Jensen
published in: Discrete Mathematics
publication date: 2010-10-18T00:00:00Z
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C60
zbMATH DE Number: 5801211
zbMATH Keywords: digraph homomorphism
zbMATH Keywords: complexity
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: NP-completeness
zbMATH Keywords: locally semicomplete digraphs
MaRDI profile type: Publication
full work available at URL: j.disc.2010.03.033
OpenAlex ID: W2036553843
cites work: Locally semicomplete digraphs: A generalization of tournaments
cites work: Digraphs
cites work: The effect of two cycles on the complexity of colourings by directed graphs
cites work: The Complexity of Colouring by Semicomplete Digraphs
cites work: Q5499919
cites work: The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
cites work: Q4198056
cites work: Polynomial graph-colorings
cites work: On the complexity of H-coloring
cites work: Q4828516
cites work: On homomorphisms to acyclic local tournaments
DOI: 10.1016/J.DISC.2010.03.033
description: scientific article; zbMATH DE number 5801211