Tight Lower Bounds for the Complexity of Multicoloring
From MaRDI portal
Publication:5111704
DOI10.4230/LIPIcs.ESA.2017.18zbMath1434.68186arXiv1607.03432OpenAlexW4391089961MaRDI QIDQ5111704
Arkadiusz Socała, Marcin Wrochna, Michał Pilipczuk, Marthe Bonamy, Łukasz Kowalik
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1607.03432
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
Unnamed Item ⋮ Tight Lower Bounds for the Complexity of Multicoloring ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- New plain-exponential time classes for graph homomorphism
- Mastermind
- Kneser's conjecture, chromatic number, and homotopy
- A simplified NP-complete satisfiability problem
- Multicoloring and Mycielski construction
- Dynamic programming based algorithms for set multicover and multiset multicover problems
- On the complexity of H-coloring
- The ellipsoid method and its consequences in combinatorial optimization
- Multicoloring trees.
- Which problems have strongly exponential complexity?
- Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems
- A technique for multicoloring triangle-free hexagonal graphs
- Exact algorithms for graph homomorphisms
- On r-Simple k-Path
- Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints
- Online Multi-Coloring with Advice
- Set Partitioning via Inclusion-Exclusion
- Two Results Concerning Multicoloring
- Channel assignment and weighted coloring
- Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
- Fractional colorings with large denominators
- Tight Lower Bounds for the Complexity of Multicoloring
- Mathematical Foundations of Computer Science 2004
- On a Combinatorial Problem in Number Theory
- Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
- Parameterized Algorithms
- Optimal reconstruction of graphs under the additive model
- On cliques in graphs
- Channel assignment and multicolouring of the induced subgraphs of the triangular lattice
- On the complexity of \(k\)-SAT
