Fine-Grained Complexity of Rainbow Coloring and its Variants.
From MaRDI portal
Publication:5111276
DOI10.4230/LIPIcs.MFCS.2017.60zbMath1441.68158OpenAlexW2771470748MaRDI QIDQ5111276
Publication date: 26 May 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8099/pdf/LIPIcs-MFCS-2017-60.pdf/
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On finding rainbow and colorful paths
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- Hardness and algorithms for rainbow connection
- On rainbow connection
- Which problems have strongly exponential complexity?
- Rainbow connections of graphs: a survey
- New Hardness Results in Rainbow Connectivity
- Rainbow Colouring of Split and Threshold Graphs
- Inapproximability of Rainbow Colouring
- Rainbow connection in graphs
- An upper bound for the harmonious chromatic number of a graph
- Upper bounds for harmonious colorings
- Color-coding
- Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
- On the Fine-Grained Complexity of Rainbow Coloring
- Tight Running Time Lower Bounds for Vertex Deletion Problems
- Parameterized Algorithms
- On the complexity of \(k\)-SAT
This page was built for publication: Fine-Grained Complexity of Rainbow Coloring and its Variants.
