Timeline for Are all subdivisions of bipartite graphs also bipartite?
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 21, 2022 at 18:39 | vote | accept | user480911 | ||
| Apr 21, 2022 at 4:37 | answer | added | usul | timeline score: 2 | |
| Apr 21, 2022 at 3:13 | comment | added | Gerry Myerson | The "new" vertices are adjacent only to "old" vertices, and the old vertices are adjacent only to new vertices, exactly as in the diagram. | |
| Apr 21, 2022 at 3:12 | history | edited | kjetil b halvorsen | CC BY-SA 4.0 |
correcting image link so image shows
|
| Apr 21, 2022 at 1:11 | comment | added | user480911 | @lambda I see, is there a formal proof for this? This is the first time I've actually seen this anywhere, and it's surprising to me that this isn't something that is taught. I can see that it does seem to be true, but I can't see how this would be applied in a general proof. | |
| Apr 20, 2022 at 18:45 | comment | added | lambda | If you subdivide every edge you get a bipartite graph regardless of what graph you started with. | |
| Apr 20, 2022 at 17:44 | comment | added | locally trivial | By a subdivision, do you mean that you are adding a new vertex in every edge between the left and right-hand subsets? Note for instance that if you don't add in a new vertex in every edge from the previous edges from left to right, then if you try to find a bipartite subdivision of the new graph via A (new vertices) and B (old vertices), then you will have some edges among the elements of B. | |
| S Apr 20, 2022 at 17:29 | review | First questions | |||
| Apr 21, 2022 at 3:12 | |||||
| S Apr 20, 2022 at 17:29 | history | asked | user480911 | CC BY-SA 4.0 |