Tight lower bounds for the complexity of multicoloring

DOI10.1145/3313906MaRDI QIDQ5205808zbMATH OpenOpenAlexWikidataFDO

Authors Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała, Marcin Wrochna

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/

zbMATH Keywords

detecting matrixexponential time hypothesishomomorphismKneser graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Tight lower bounds for the complexity of multicoloring
• Lower bounds for the graph homomorphism problem
• Finer tight bounds for coloring on clique-width
• Finer tight bounds for coloring on clique-width
• Tight lower bounds for list edge coloring

Cited in

(13)

• Sequential coloring versus Welsh-Powell bound
• Lower bounds on strip discrepancy for nonatomic colorings
• Optimal bounds for the colored Tverberg problem
• Tight lower and upper bounds for the complexity of canonical colour refinement
• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
• scientific article; zbMATH DE number 1114021 (Why is no real title available?)
• Tight lower bounds for the complexity of multicoloring
• Graph-Theoretic Concepts in Computer Science
• On low rank-width colorings
• Disentangling the computational complexity of network untangling
• Counting homomorphisms in plain exponential time
• Linear programming complementation
• Structural parameterizations for two bounded degree problems revisited

This page was built for publication: Tight lower bounds for the complexity of multicoloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5205808)