Fine-Grained Complexity of Rainbow Coloring and its Variants.
DOI10.4230/LIPICS.MFCS.2017.60zbMATH Open1441.68158OpenAlexW2771470748MaRDI QIDQ5111276FDOQ5111276
Authors: Akanksha Agrawal 
Publication date: 26 May 2020
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8099/pdf/LIPIcs-MFCS-2017-60.pdf/
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Title not available (Why is that?)
- On rainbow connection
- Which problems have strongly exponential complexity?
- On finding rainbow and colorful paths
- Rainbow connection in graphs
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- Title not available (Why is that?)
- Color-coding
- Lower bounds based on the exponential time hypothesis
- Hardness and algorithms for rainbow connection
- Parameterized algorithms
- On the complexity of \(k\)-SAT
- Chromatic graph theory
- Rainbow connectivity: hardness and tractability
- Title not available (Why is that?)
- Rainbow Colouring of Split and Threshold Graphs
- Inapproximability of Rainbow Colouring
- An upper bound for the harmonious chromatic number of a graph
- On the fine-grained complexity of rainbow coloring
- Title not available (Why is that?)
- Tight running time lower bounds for vertex deletion problems
- Upper bounds for harmonious colorings
- Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
Cited In (9)
- On finding rainbow and colorful paths
- On the complexity of \(k\)-rainbow cycle colouring problems
- Inapproximability of Rainbow Colouring
- Rainbow vertex coloring bipartite graphs and chordal graphs
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
- The algorithmic complexity of colour switching
- On the fine-grained complexity of rainbow coloring
- On the fine-grained complexity of rainbow coloring
- Fine-grained complexity of rainbow coloring and its variants
This page was built for publication: Fine-Grained Complexity of Rainbow Coloring and its Variants.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111276)
