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

✍ Scribed by Carsten Thomassen

• Publisher: John Wiley and Sons
• Year: 2006
• Tongue: English
• Weight: 109 KB
• Volume: 53
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20178

✦ Synopsis

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. 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