Timeline for bounded degree graph colouring.
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 20, 2016 at 11:17 | comment | added | Pavan Sangha | yes i see this, how can we increase $k$ though? Maybe add a clique instead? | |
| May 18, 2016 at 6:12 | comment | added | joro | The starting point for $k=3$ is $d=4$ -- the line graph of 3-regular graph for which edge coloring is NP-hard. To get $d=5$ add new vertex and an edge to any of the vertices, this doesn't change the chromatic number. | |
| May 17, 2016 at 22:30 | comment | added | Pavan Sangha | Could you elaborate slightly? Are you saying for a fixed bounded degree $d$ we can prove hardness for all $k \leq d$ by making some sort of reduction which adds a bipartite star graph? If so where is the starting point of hardness $k=3$? | |
| May 10, 2016 at 12:04 | comment | added | joro | You can artificially increase the degree by adding a bipartite star graph. | |
| May 10, 2016 at 11:04 | history | asked | Pavan Sangha | CC BY-SA 3.0 |