Timeline for Red-blue alternating paths
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 26, 2015 at 20:35 | history | edited | domotorp | CC BY-SA 3.0 |
added 290 characters in body
|
| Jun 23, 2015 at 8:13 | answer | added | David Herskovics | timeline score: 1 | |
| Aug 8, 2014 at 4:48 | comment | added | domotorp | @Per: On the other hand, maybe it is enough to demand one degree less in, say, the blue graph. | |
| Aug 8, 2014 at 4:47 | comment | added | domotorp | @Per: Yes. Suppose both graphs are the same and the vertex set is $v_1, \ldots, v_k, u_1, \ldots, u_k$ and the edges are $v_iu_j$ if and only if $i\le j$. In this case the only solution is to take all $k$ single-edge paths $v_iu_i$. If you delete any of these edges, the statement becomes false. | |
| Aug 7, 2014 at 19:53 | comment | added | Per Alexandersson | Is the condition that $\deg(v_i)\geq i$ of special importance? It seems a bit surprising, is this sharp in some sense? | |
| Jan 20, 2010 at 12:45 | history | edited | Andrew Stacey | CC BY-SA 2.5 |
cleaned up formatting
|
| Jan 20, 2010 at 12:32 | history | asked | domotorp | CC BY-SA 2.5 |