Nowhere-zero 6-flows

P. D. Seymour

doi:10.1016/0095-8956(81)90058-7

Nowhere-zero 6-flows

P. D. Seymour

Research output: Contribution to journal › Article › peer-review

186 Scopus citations

Abstract

We prove that every graph with no isthmus has a nowhere-zero 6-flow, that is, a circulation in which the value of the flow through each edge is one of ±1, ±2,..., ±5. This improves Jaeger's 8-flow theorem, and approaches Tutte's 5-flow conjecture.

Original language	English (US)
Pages (from-to)	130-135
Number of pages	6
Journal	Journal of Combinatorial Theory, Series B
Volume	30
Issue number	2
DOIs	https://doi.org/10.1016/0095-8956(81)90058-7
State	Published - Apr 1981
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0095-8956(81)90058-7

Cite this

@article{bd8f6c7e6636441e9c574803c1b95f30,

title = "Nowhere-zero 6-flows",

abstract = "We prove that every graph with no isthmus has a nowhere-zero 6-flow, that is, a circulation in which the value of the flow through each edge is one of ±1, ±2,..., ±5. This improves Jaeger's 8-flow theorem, and approaches Tutte's 5-flow conjecture.",

author = "Seymour, {P. D.}",

year = "1981",

month = apr,

doi = "10.1016/0095-8956(81)90058-7",

language = "English (US)",

volume = "30",

pages = "130--135",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Nowhere-zero 6-flows

AU - Seymour, P. D.

PY - 1981/4

Y1 - 1981/4

N2 - We prove that every graph with no isthmus has a nowhere-zero 6-flow, that is, a circulation in which the value of the flow through each edge is one of ±1, ±2,..., ±5. This improves Jaeger's 8-flow theorem, and approaches Tutte's 5-flow conjecture.

AB - We prove that every graph with no isthmus has a nowhere-zero 6-flow, that is, a circulation in which the value of the flow through each edge is one of ±1, ±2,..., ±5. This improves Jaeger's 8-flow theorem, and approaches Tutte's 5-flow conjecture.

UR - http://www.scopus.com/inward/record.url?scp=0001342026&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0001342026&partnerID=8YFLogxK

U2 - 10.1016/0095-8956(81)90058-7

DO - 10.1016/0095-8956(81)90058-7

M3 - Article

AN - SCOPUS:0001342026

SN - 0095-8956

VL - 30

SP - 130

EP - 135

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -

Nowhere-zero 6-flows

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this