Timeline for A Conjecture About Directed Graphs that are the Union of Two Trees
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Aug 12, 2014 at 1:42 | comment | added | Gerry Myerson | Where is the example of Chudnovsky & Seymour? | |
| Aug 11, 2014 at 20:18 | history | edited | Gil Kalai | CC BY-SA 3.0 |
added 410 characters in body
|
| Feb 7, 2013 at 16:28 | comment | added | Gil Kalai | The answer is NO as pointed out by an (embarrassingly simple) example by Maria Chudnovsky and Paul Seymour, who also pointed out additional necessary conditions. | |
| Jun 9, 2012 at 21:39 | comment | added | Gil Kalai | Dear Flo, hmm the way I thought about it is that the trees are not rooted and are directed in an arbitrary way. So the initial condition just say that D is the union of two spanning trees (when we forget about how the edges are directed,) and the conjecture is that, when we remember again the way the edges are directed, then unless we have a cut consisting just of two edges with reverse directions, we can actualy find two edge disjoint trees that reversing the direction in one lead to a strongly connected graph. So I thought about your version 2. | |
| Jun 8, 2012 at 8:04 | comment | added | Flo Pfender | Gil, when you say "directed trees", do you mean 1) rooted tree, and all edges directed away from it, or 2) tree with all edges directed some way? | |
| Jun 7, 2012 at 19:28 | comment | added | Gil Kalai | Dear Benjamin, not at all. | |
| Jun 7, 2012 at 16:38 | comment | added | Benjamin Young | Should the two directed spanning trees comprising D have the same root? | |
| Jun 5, 2012 at 22:05 | comment | added | Vidit Nanda | I wonder if anyone else has also spent the last 2 hours attempting counterexamples :( | |
| Jun 5, 2012 at 18:46 | history | asked | Gil Kalai | CC BY-SA 3.0 |