Timeline for Jordan-like cycles in graphs
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 15, 2013 at 8:09 | vote | accept | Hans-Peter Stricker | ||
| Jan 14, 2013 at 23:39 | comment | added | Aaron Meyerowitz | I guess what I said wasn't enough, But the cycle could be a 3 cycle. | |
| Jan 14, 2013 at 18:07 | history | edited | Ben Barber | CC BY-SA 3.0 |
Correct and clarify
|
| Jan 14, 2013 at 17:34 | comment | added | Ben Barber | Yes, I reversed the definition by mistake - I was thinking in terms of "can be drawn with everything inside". I'll edit the answer soon, but first I'd like to double check your final comment: I still think all four vertices need to be distinct to find an obstruction to the "all inside" drawing. | |
| Jan 14, 2013 at 17:03 | comment | added | Aaron Meyerowitz | I like the idea, that looks be the answer (provided that being planar is assumed), but you seem to have stated the condition for $\gamma$ to not be a Jordan cycle. So: Let $\gamma$ be a cycle such that $G - \gamma$ has exactly two connected components. Let $S_1,S_2$ be as you say. The condition for $\gamma$ to be a Jordon cycle is that there are 4 vertices $x_1 \ne y_1 \ne x_2 \ne y_2$ (but $x_1=y_2$ is ok) in cyclic order around $\gamma$ so that $x_i \in S_1$ and $y_i \in S_2.$ | |
| Jan 14, 2013 at 15:36 | comment | added | Hans-Peter Stricker | @Ben: thanks for the clarification! | |
| Jan 14, 2013 at 15:29 | comment | added | Ben Barber | I intended to answer question 1; sorry for not making that clear. Here's a picture that might help: imagine holding the graph up in $\mathbb{R}^3$; $\gamma$ is Jordan if and only if $G_1$ and $G_2$ can't rotate freely past each other around $\gamma$. The above is just one way of writing that down. I don't have a better answer for 2 than "check the condition for every cycle of $G$". | |
| Jan 14, 2013 at 15:08 | comment | added | Hans-Peter Stricker | Please give me a clue which question you aim to answer? (Maybe my definition contains a flaw, and you want to give me a hint to that?) | |
| Jan 14, 2013 at 15:02 | history | answered | Ben Barber | CC BY-SA 3.0 |