Timeline for A method for making a graph bipartite
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 25, 2020 at 7:23 | history | edited | Timothy Budd | CC BY-SA 4.0 |
Source links to my old website are broken, so I removed them.
|
| S Sep 11, 2017 at 23:17 | history | suggested | jeq | CC BY-SA 3.0 |
Copied images to imgur.com, as they were not being displayed because of new https rule. Added links to original image sources.
|
| Sep 11, 2017 at 23:06 | review | Suggested edits | |||
| S Sep 11, 2017 at 23:17 | |||||
| Sep 9, 2014 at 17:08 | comment | added | Timothy Budd | Not all bipartite subgraphs can occur as result of the algorithm. It turns out that (at least I checked for $5\leq n\leq 11$) that the largest such subgraph that can occur is the $(n-3)+3$ one. One should probably carefully consider the possibilities at each step to understand why, or perhaps there is a simple argument that I don't know. | |
| Sep 9, 2014 at 16:52 | comment | added | Benoît Kloeckner | I don't understand your second edit: what about the complete bipartite graph with $n/2+n/2$ vertices? | |
| Sep 9, 2014 at 16:42 | vote | accept | CoffeeCat | ||
| Sep 9, 2014 at 16:33 | comment | added | bbejot | +1 for pretty graphs | |
| Sep 9, 2014 at 9:48 | history | edited | Timothy Budd | CC BY-SA 3.0 |
Added complete graph counterexample
|
| Sep 9, 2014 at 9:22 | history | edited | Timothy Budd | CC BY-SA 3.0 |
Added link to Mathematica code.
|
| Sep 9, 2014 at 8:53 | history | edited | Timothy Budd | CC BY-SA 3.0 |
Added new counterexample.
|
| Sep 9, 2014 at 8:34 | comment | added | Timothy Budd | Yes, you are right. I guess the real question is: do graphs exist for which any sequence of edge removals (belonging to most odd cycles) leads to a bipartite graph with less than $e(G)/2$ edges. | |
| Sep 9, 2014 at 8:26 | comment | added | The Masked Avenger | Or 8 edges also. (Start by removing the red square.) | |
| Sep 9, 2014 at 8:12 | history | answered | Timothy Budd | CC BY-SA 3.0 |