Timeline for Is Max-Cut APX-complete on triangle-free graphs?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 16, 2011 at 19:38 | comment | added | Standa Zivny | Thank you Colin! While looking for an answer, I've discovered the same trick you call "3-stretch", also known as 2-subdivision. From what I've found, it probably first appeared in this paper: Svatopluk Poljak: A note on stable sets and colouring of graphs, Comment. Math. Univ. Carolinae 15 (1974) 307-309 (available here: dml.cz/handle/10338.dmlcz/105554) | |
| Oct 16, 2011 at 19:30 | vote | accept | Standa Zivny | ||
| Oct 16, 2011 at 17:10 | history | answered | Colin McQuillan | CC BY-SA 3.0 |