On the fine-grained complexity of rainbow coloring

DOI10.1137/16M1102690MaRDI QIDQ3174728zbMATH OpenOpenAlexWikidataFDO

Authors Łukasz Kowalik, Juho Lauri, Arkadiusz Socała

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

zbMATH Keywords

computational complexitylower boundsgraph coloringFPT algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Coloring of graphs and hypergraphs (05C15)

Recommendations

• On the fine-grained complexity of rainbow coloring
• Fine-grained complexity of rainbow coloring and its variants
• Fine-Grained Complexity of Rainbow Coloring and its Variants.
• On finding rainbow and colorful paths
• The parameterized complexity of the rainbow subgraph problem

Cites work

• scientific article; zbMATH DE number 5776838 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• A Dynamic Programming Approach to Sequencing Problems
• A note on the complexity of the chromatic number problem
• A simplified NP-complete satisfiability problem
• Chromatic graph theory
• Hardness and algorithms for rainbow connection
• Inapproximability of Rainbow Colouring
• On rainbow connection
• On set intersection representations of graphs
• 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 colouring of split graphs
• Rainbow connection in graphs
• Rainbow connectivity: hardness and tractability
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Tight lower bound for the channel assignment problem
• Which problems have strongly exponential complexity?

Cited in

(14)

• A survey on rainbow (vertex-)index of graphs
• On finding rainbow and colorful paths
• The parameterized complexity of the rainbow subgraph problem
• The parameterized complexity of the rainbow subgraph problem
• On the complexity of \(k\)-rainbow cycle colouring problems
• Inapproximability of Rainbow Colouring
• The maximum 2-edge-colorable subgraph problem and its fixed-parameter tractability
• Fine-Grained Complexity of Rainbow Coloring and its Variants.
• Your rugby mates don't need to know your colleagues: triadic closure with edge colors
• On the complexity of rainbow vertex colouring diametral path graphs
• The algorithmic complexity of colour switching
• Quadratic vertex kernel for rainbow matching
• On the fine-grained complexity of rainbow coloring
• Fine-grained complexity of rainbow coloring and its variants

This page was built for publication: On the fine-grained complexity of rainbow coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3174728)