𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on line digraphs and the directed max-cut problem

✍ Scribed by V. Chvátal; C. Ebenegger

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
365 KB
Volume
29
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

Note on the existence of directed (k + 1
Note on the existence of directed (k + 1)-cycles in diconnected complete k-partite digraphs
✍ R. Balakrishnan; P. Paulraja 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views

A graph is constructed to provide a negative answer to the following question of Bondy: Does every diconnected orientation of a complete k-partite (k 2 5) graph with each part of size at least 2 yield a directed (k + 1)-cycle?