✦ LIBER ✦

Hypothetical complexity of the nowhere-zero 5-flow problem

✍ Scribed by Kochol, Martin

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 251 KB
Volume: 28
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199805)28:1<1::aid-jgt1>3.0.co;2-q

No coin nor oath required. For personal study only.

✦ Synopsis

We show that if the well-known 5-Flow Conjecture of Tutte is not true, then the problem to determine whether a (cubic) graph admits a nowherezero 5-flow is NP-complete.

📜 SIMILAR VOLUMES

The size of graphs without nowhere-zero

The size of graphs without nowhere-zero 4-flows

✍ Hong-Jian Lai 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 428 KB 👁 1 views

Let G be a 2-edge-connected simple graph with order n. We show that if IV(G)l 5 17, then either G has a nowhere-zero 4-flow, or G is contractible to the Petersen graph. We also show that for n large, if I€(G)J L (' 2 17) + 34, then either G has a nonwhere-zero 4-flow, or G can be contracted to the P

The complexity of minimum cut and maximu

The complexity of minimum cut and maximum flow problems in an acyclic network

✍ Vijaya Ramachandran 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 314 KB