Fine-grained complexity of rainbow coloring and its variants

DOI10.1016/j.jcss.2021.10.001zbMath1481.68033OpenAlexW3205160705MaRDI QIDQ2051859

Akanksha Agrawal

Publication date: 25 November 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8099/

zbMATH Keywords

lower boundrainbow coloringETHfine-grained complexity

Mathematics Subject Classification ID

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 (1)

A survey on rainbow (vertex-)index of graphs

Cites Work

• Unnamed Item
• 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
• Parametrized complexity theory.
• New Hardness Results in Rainbow Connectivity
• Rainbow Colouring of Split and Threshold Graphs
• Inapproximability of Rainbow Colouring
• On the Fine-Grained Complexity of Rainbow Coloring
• 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