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/

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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Fine-grained complexity of rainbow coloring and its variants
• On the fine-grained complexity of rainbow coloring
• On the fine-grained complexity of rainbow coloring
• On finding rainbow and colorful paths

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 1057876 (Why is no real title available?)
• scientific article; zbMATH DE number 6862097 (Why is no real title available?)
• An upper bound for the harmonious chromatic number of a graph
• Chromatic graph theory
• Color-coding
• Hardness and algorithms for rainbow connection
• Inapproximability of Rainbow Colouring
• Lower bounds based on the exponential time hypothesis
• On finding rainbow and colorful paths
• On rainbow connection
• On the complexity of \(k\)-SAT
• On the fine-grained complexity of rainbow coloring
• On the rainbow connectivity of graphs: complexity and FPT algorithms
• Parameterized algorithms
• Rainbow Colouring of Split and Threshold Graphs
• Rainbow connection in graphs
• Rainbow connectivity: hardness and tractability
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Tight running time lower bounds for vertex deletion problems
• Upper bounds for harmonious colorings
• Which problems have strongly exponential complexity?

Cited in

(9)

• Fine-grained complexity of rainbow coloring and its variants
• The algorithmic complexity of colour switching
• On the complexity of \(k\)-rainbow cycle colouring problems
• Inapproximability of Rainbow Colouring
• On the fine-grained complexity of rainbow coloring
• On the fine-grained complexity of rainbow coloring
• Rainbow vertex coloring bipartite graphs and chordal graphs
• On finding rainbow and colorful paths
• Your rugby mates don't need to know your colleagues: triadic closure with edge colors

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)