Tight Lower Bounds for the Complexity of Multicoloring
From MaRDI portal
Publication:5205808
DOI10.1145/3313906zbMath1434.68185OpenAlexW2962825993WikidataQ128121205 ScholiaQ128121205MaRDI QIDQ5205808
Marcin Wrochna, Marthe Bonamy, Arkadiusz Socała, Michał Pilipczuk, Łukasz Kowalik
Publication date: 16 December 2019
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7852/
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items