On the Fine-Grained Complexity of Rainbow Coloring
From MaRDI portal
Publication:3174728
DOI10.1137/16M1102690zbMath1395.05060OpenAlexW2963963322WikidataQ129519337 ScholiaQ129519337MaRDI QIDQ3174728
Juho Lauri, Arkadiusz Socała, Łukasz Kowalik
Publication date: 18 July 2018
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1102690
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
A survey on rainbow (vertex-)index of graphs ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ Fine-grained complexity of rainbow coloring and its variants
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Rainbow colouring of split graphs
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- Hardness and algorithms for rainbow connection
- A simplified NP-complete satisfiability problem
- On rainbow connection
- A note on the complexity of the chromatic number problem
- Which problems have strongly exponential complexity?
- On the complexity of rainbow coloring problems
- Rainbow connections of graphs: a survey
- New Hardness Results in Rainbow Connectivity
- Rainbow Colouring of Split and Threshold Graphs
- Inapproximability of Rainbow Colouring
- A Dynamic Programming Approach to Sequencing Problems
- Rainbow connection in graphs
- On set intersection representations of graphs
- Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
- On the Fine-Grained Complexity of Rainbow Coloring
- Tight lower bound for the channel assignment problem
- Parameterized Algorithms
- On the complexity of \(k\)-SAT
This page was built for publication: On the Fine-Grained Complexity of Rainbow Coloring
