The Complexity of Colouring by Semicomplete Digraphs
From MaRDI portal
Publication:3834066
DOI10.1137/0401029zbMath0678.05018OpenAlexW2051731147MaRDI 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
complexityNP-completenessdirected graphtournamentsgraph colouringgraph homomorphismpolynomial algorithmH-colouring problemsemicomplete digraphsT-colouring problem
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)
Related Items
The complexity of colouring symmetric relational systems ⋮ Quantified Constraint Satisfaction Problem on Semicomplete Digraphs ⋮ Graph homomorphisms with infinite targets ⋮ Homomorphisms to oriented paths ⋮ Oriented incidence colourings of digraphs ⋮ Complexity and polymorphisms for digraph constraint problems under some basic constructions ⋮ Unnamed Item ⋮ The complexity of restricted graph homomorphisms ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ Homomorphically full graphs ⋮ Analogues of cliques for \((m,n)\)-colored mixed graphs ⋮ Complexity of tree homomorphisms ⋮ List homomorphisms to reflexive graphs ⋮ Oriented coloring in planar, bipartite, bounded degree 3 acyclic oriented graphs ⋮ The effect of two cycles on the complexity of colourings by directed graphs ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Homomorphisms and oriented colorings of equivalence classes of oriented graphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ Quantified Constraints in Twenty Seventeen ⋮ Path homomorphisms ⋮ Polynomial graph-colorings ⋮ Minimum cost homomorphisms to semicomplete multipartite digraphs ⋮ On the complexity of colouring by superdigraphs of bipartite graphs ⋮ The core of a graph ⋮ The complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops ⋮ The complexity of tropical graph homomorphisms ⋮ Minimum cost and list homomorphisms to semicomplete digraphs ⋮ The complexity of colouring by locally semicomplete digraphs ⋮ Unnamed Item ⋮ Graph partitions with prescribed patterns ⋮ Dichotomy for finite tournaments of mixed-type ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs ⋮ Polynomial graph-colorings ⋮ Chromatic polynomials of oriented graphs ⋮ The recognition of bound quivers using edge-coloured homomorphisms ⋮ Hereditarily hard \(H\)-colouring problems ⋮ Core-like properties of infinite graphs and structures ⋮ Locally Semicomplete Digraphs and Generalizations ⋮ Homomorphisms to oriented cycles ⋮ List homomorphism problems for signed trees
