Timeline for Known bounds of the maximum cut of planar graphs
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 24, 2023 at 20:43 | comment | added | Pranay Gorantla | The following post on mathSE addresses the lower bound: math.stackexchange.com/questions/1918960/…. This lower bound is tight and is obtained by maximal planar graphs. | |
| Mar 4, 2022 at 9:54 | history | edited | Licheng Zhang | CC BY-SA 4.0 |
added 54 characters in body
|
| Mar 4, 2022 at 9:50 | comment | added | Licheng Zhang | Thanks, Sir. I noticed that there was some discussion about the lower bounds of the maximum cut for some graphs. [AS B B, SCOTT A D. Better Bounds for Max Cut[J]] ., but I didn't see anything talk about planar graph. | |
| Mar 4, 2022 at 6:59 | comment | added | Brendan McKay | A cut in a triangulation can't use all three edges of a face, so an upper bound is two edges from each face. This is achieved by triangulations whose dual is hamiltonian. | |
| Mar 4, 2022 at 6:11 | history | edited | YCor | CC BY-SA 4.0 |
removed capitals, added tag
|
| Mar 4, 2022 at 1:50 | history | asked | Licheng Zhang | CC BY-SA 4.0 |