Timeline for An edge partitioning problem on cubic graphs
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 3, 2010 at 7:26 | comment | added | Anthony Labarre | Thanks for pointing out the missing bit, I modified my question accordingly. | |
| Nov 2, 2010 at 23:43 | history | edited | Dave Pritchard | CC BY-SA 2.5 |
added 82 characters in body
|
| Nov 2, 2010 at 22:33 | comment | added | Anthony Labarre | A cubic graph (and actually, any $k$-regular graph with $k$ odd) cannot be partitioned into triangles. I agree that intuition would suggest that maximizing the number of triangles would be the way to go, but the following counterexample will convince you otherwise: take the complement of a cycle of length 6 (wwwteo.informatik.uni-rostock.de/isgci/images/g_co-C6.gif). If you use both triangles, you get a solution of weight 12, while discarding one triangle gives you a solution of weight 11. | |
| Nov 2, 2010 at 21:05 | history | edited | Dave Pritchard | CC BY-SA 2.5 |
added 23 characters in body
|
| Nov 2, 2010 at 20:56 | history | answered | Dave Pritchard | CC BY-SA 2.5 |
