On the complexity of the general coloring problem
From MaRDI portal
Publication:3968465
DOI10.1016/S0019-9958(81)90226-6zbMath0502.68015OpenAlexW2038074073WikidataQ54310125 ScholiaQ54310125MaRDI QIDQ3968465
J. H. Sudborough, Hermann Maurer, Ermo Welzl
Publication date: 1981
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(81)90226-6
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Graph homomorphisms with infinite targets, Homomorphisms to oriented paths, On the complexity of H-coloring, The complexity of restricted graph homomorphisms, Digraph matrix partitions and trigraph homomorphisms, List homomorphisms of graphs with bounded degrees, Complexity of tree homomorphisms, The effect of two cycles on the complexity of colourings by directed graphs, Unnamed Item, Homomorphisms and oriented colorings of equivalence classes of oriented graphs, Path homomorphisms, Polynomial graph-colorings, On the General Coloring Problem, On the complexity of colouring by superdigraphs of bipartite graphs, On Sabidussi--Fawcett subdirect representation, Graph theory (algorithmic, algebraic, and metric problems), Dichotomy for finite tournaments of mixed-type, Dichotomy for bounded degree \(H\)-colouring, \(H\)-coloring degree-bounded (acyclic) digraphs, Polynomial graph-colorings, Homomorphisms of hexagonal graphs to odd cycles, Hereditarily hard \(H\)-colouring problems, Symmetric graphs and interpretations, Homomorphisms of 3-chromatic graphs, Concerning the achromatic number of graphs, Homomorphisms to oriented cycles
