Timeline for Is there easy proof for triangle-free two-coloring of planar graphs?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 2, 2016 at 13:29 | comment | added | Louis Esperet | By the way the proof of Burstein is fairly simple. For 4-connected triangulations, this is just a consequence of the fact that bridgeless cubic graphs have a perfect matching containing any given edge (since 2-colorings of planar triangulations without monochromatic faces are in 1-to-1 correspondence with perfect matchings of the dual graph). If the triangulation is not 4-connected, a simple induction finishes the proof by removing the interior of a separating triangle. | |
| Dec 2, 2016 at 0:28 | vote | accept | domotorp | ||
| Dec 1, 2016 at 22:06 | history | answered | Gjergji Zaimi | CC BY-SA 3.0 |