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
- A Dynamic Programming Approach to Sequencing Problems
- On rainbow connection
- Which problems have strongly exponential complexity?
- Rainbow connection in graphs
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- Title not available (Why is that?)
- Hardness and algorithms for rainbow connection
- Parameterized algorithms
- On the complexity of \(k\)-SAT
- A simplified NP-complete satisfiability problem
- On set intersection representations of graphs
- Tight lower bound for the channel assignment problem
- Chromatic graph theory
- Rainbow connectivity: hardness and tractability
- A note on the complexity of the chromatic number problem
- Rainbow Colouring of Split and Threshold Graphs
- Inapproximability of Rainbow Colouring
- Rainbow colouring of split graphs
- Title not available (Why is that?)
- On the fine-grained complexity of rainbow coloring
- Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
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)
