𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The max-cut problem on graphs not contractible to K5

✍ Scribed by Francisco Barahona

Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
454 KB
Volume
2
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The performance of an eigenvalue bound o
The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
✍ C. Delorme; S. Poljak πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 683 KB

Delorme, C. and S. Poljak, The performance of an eigenvalue bound on the max-cut problem in some classes of graphs, Discrete Mathematics 111 (1993) 145-156. The authors earlier introduced a number q(C), which gives a well-computable upper bound on the maximum bipartite subgraph of a graph or, more

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