One strike against the min-max degree triangulation problem

On the max-cut problem for a planar, cub

On the max-cut problem for a planar, cubic, triangle-free graph, and the Chinese postman problem for a planar triangulation

✍ Carsten Thomassen 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 109 KB 👁 2 views

## Abstract Every 3‐connected planar, cubic, triangle‐free graph with __n__ vertices has a bipartite subgraph with at least 29__n__/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. Example