Timeline for Is 3-coloring bounded degree graphs subexponential: $O(\exp{(\sqrt{n}\log^2{n})})$?
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 4, 2018 at 16:45 | comment | added | D.W. | Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. | |
| May 3, 2018 at 16:32 | comment | added | Emil Jeřábek | “$O(n\log^4n)$-approximation” does not mean a drawing with $O(n\log^4n)$ crossings, but a drawing whose number of crossings is at most $O(n\log^4n)$-times higher than in the optimal drawing. (Also, this is not what the paper proves, but an old result on which it improves.) | |
| May 3, 2018 at 16:17 | comment | added | Emil Jeřábek | Cross-posted to cstheory.stackexchange.com/q/40723 | |
| May 3, 2018 at 13:45 | history | asked | joro | CC BY-SA 4.0 |