Timeline for Necessary Conditions for a Graph not possible to Rainbow Color?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 26, 2019 at 20:08 | history | edited | Ryan Dougherty | CC BY-SA 4.0 |
NP-hardness shown
|
| Feb 26, 2019 at 20:05 | comment | added | Ryan Dougherty | @user36212 I see, thank you for explicitly giving the reduction! This does indeed show hardness for $v > t$. | |
| Feb 26, 2019 at 19:09 | comment | added | user36212 | For t=2,v=3 your problem is exactly graph-3-colouring, right? And now to go up in uniformity from this, for general t and v=t+1 take a 2-graph G, add t-2 vertices, and put t-edges containing all the new vertices plus each edge of G. To rainbow colour the resulting graph with v colours, you need to use one colour per new vertex and then G must be 3-colourable, so your problem is NP-hard for v=t+1 and this generalises easily for fixed v>t. | |
| Feb 26, 2019 at 15:15 | comment | added | Ryan Dougherty | @user36212 I think you're doing the reduction in the wrong direction. And the "NP-hard" type question here would be to find a maximum size subgraph without an induced copy of $G$. For $t=2$, this turns out to be equivalent to the Max 2-SAT problem, but the condition for $G$ to be avoided is easy to state. | |
| Feb 26, 2019 at 14:01 | comment | added | user36212 | This problem is well known to be NP-hard (see the book by Garey and Johnson, or simply use the obvious reduction to graph colouring for v>t). So you should expect that no simple necessary and sufficient conditions exist. | |
| Feb 26, 2019 at 13:28 | history | edited | Ryan Dougherty | CC BY-SA 4.0 |
infinite family found
|
| Feb 25, 2019 at 1:25 | history | asked | Ryan Dougherty | CC BY-SA 4.0 |