On the max‐cut problem for a planar, cubic, triangle‐free graph, and the Chinese postman problem for a planar triangulation
Carsten Thomassen · Journal of Graph Theory · 2006
Abstract Every 3‐connected planar, cubic, triangle‐free graph with n vertices has a bipartite subgraph with at least 29n/24 − 7/6 edges. The constant 29/24 improves the previously best known constant 6/5 which was considered best possible because of the graph of the dodecahedron. Examples show that the constant 29/24 = 1.2083… cannot be raised to more than 47/38 = 1.2368…. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 261–269, 2006