On the complexity of the general coloring problem
From MaRDI portal
Publication:3968465
DOI10.1016/S0019-9958(81)90226-6zbMATH Open0502.68015DBLPjournals/iandc/MaurerSW81bOpenAlexW2038074073WikidataQ54310125 ScholiaQ54310125MaRDI QIDQ3968465FDOQ3968465
Authors: Hermann Maurer, J. H. Sudborough, Emo 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)
Cited In (26)
- The complexity of restricted graph homomorphisms
- Concerning the achromatic number of graphs
- On Sabidussi--Fawcett subdirect representation
- Polynomial graph-colorings
- Graph homomorphisms with infinite targets
- Polynomial graph-colorings
- Homomorphisms of 3-chromatic graphs
- Dichotomy for finite tournaments of mixed-type
- On the complexity of H-coloring
- Path homomorphisms
- Homomorphisms to oriented cycles
- Graph theory (algorithmic, algebraic, and metric problems)
- Sparsification lower bounds for list \(H\)-coloring
- Homomorphisms and oriented colorings of equivalence classes of oriented graphs
- On the general coloring problem
- \(H\)-coloring degree-bounded (acyclic) digraphs
- On the complexity of colouring by superdigraphs of bipartite graphs
- Dichotomy for bounded degree \(H\)-colouring
- List homomorphisms of graphs with bounded degrees
- The effect of two cycles on the complexity of colourings by directed graphs
- Digraph matrix partitions and trigraph homomorphisms
- Hereditarily hard \(H\)-colouring problems
- Symmetric graphs and interpretations
- Complexity of tree homomorphisms
- Homomorphisms of hexagonal graphs to odd cycles
- Homomorphisms to oriented paths
This page was built for publication: On the complexity of the general coloring problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3968465)
