On the fine-grained complexity of rainbow coloring
DOI10.1137/16M1102690zbMATH Open1395.05060OpenAlexW2963963322WikidataQ129519337 ScholiaQ129519337MaRDI QIDQ3174728FDOQ3174728
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
Recommendations
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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 (13)
- The parameterized complexity of the rainbow subgraph problem
- The parameterized complexity of the rainbow subgraph problem
- On finding rainbow and colorful paths
- 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
- 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
- A survey on rainbow (vertex-)index of graphs
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)
