On the Fine-Grained Complexity of Rainbow Coloring
DOI10.1137/16M1102690zbMATH Open1395.05060OpenAlexW2963963322WikidataQ129519337 ScholiaQ129519337MaRDI QIDQ3174728FDOQ3174728
Juho Lauri, Arkadiusz Socała, Łukasz Kowalik
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
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?)
- Title not available (Why is that?)
- A Dynamic Programming Approach to Sequencing Problems
- On rainbow connection
- Which problems have strongly exponential complexity?
- Rainbow connections of graphs: a survey
- Rainbow connection in graphs
- On the rainbow connectivity of graphs: complexity and FPT algorithms
- 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
- 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
- On the complexity of rainbow coloring problems
- On the Fine-Grained Complexity of Rainbow Coloring
- Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
Cited In (7)
- 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
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
- The algorithmic complexity of colour switching
- 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)
