The Complexity of Colouring by Semicomplete Digraphs
From MaRDI portal
Publication:3834066
DOI10.1137/0401029zbMath0678.05018MaRDI QIDQ3834066
Gary MacGillivray, Pavol Hell, Jörgen Bang-Jensen
Publication date: 1988
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0401029
complexity; NP-completeness; directed graph; tournaments; graph colouring; graph homomorphism; polynomial algorithm; H-colouring problem; semicomplete digraphs; T-colouring problem
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
05C20: Directed graphs (digraphs), tournaments
Related Items
Path homomorphisms, On the complexity of colouring by superdigraphs of bipartite graphs, The core of a graph, The complexity of colouring by locally semicomplete digraphs, Digraph matrix partitions and trigraph homomorphisms, The effect of two cycles on the complexity of colourings by directed graphs, Minimum cost homomorphisms to semicomplete multipartite digraphs, The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops, List homomorphisms to reflexive graphs, Polynomial graph-colorings, Homomorphisms to oriented cycles, The complexity of colouring symmetric relational systems, Graph homomorphisms with infinite targets, Homomorphisms to oriented paths, The complexity of restricted graph homomorphisms, Homomorphisms and oriented colorings of equivalence classes of oriented graphs, Hereditarily hard \(H\)-colouring problems, Core-like properties of infinite graphs and structures, Homomorphically full graphs, Complexity of tree homomorphisms, Minimum cost and list homomorphisms to semicomplete digraphs, The recognition of bound quivers using edge-coloured homomorphisms
