Almost all 5-regular graphs have a 3-flow

Paweł Prałat; Nick Wormald

doi:10.1002/jgt.22478

Almost all 5-regular graphs have a 3-flow

Paweł Prałat, Nick Wormald

School of Mathematics

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

Abstract

Tutte conjectured in 1972 that every 4-edge–connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge–connected graph has an edge orientation in which every in-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge–connected 5-regular graphs.

Original language	English
Pages (from-to)	147-156
Number of pages	10
Journal	Journal of Graph Theory
Volume	93
Issue number	2
DOIs	https://doi.org/10.1002/jgt.22478
Publication status	Published - 1 Feb 2020

Keywords

3-flow
random graphs
small subgraph conditioning method

Cite this

Prałat, P., & Wormald, N. (2020). Almost all 5-regular graphs have a 3-flow. Journal of Graph Theory, 93(2), 147-156. https://doi.org/10.1002/jgt.22478

@article{3e58e475414243a6a37674b75b857cea,

title = "Almost all 5-regular graphs have a 3-flow",

abstract = "Tutte conjectured in 1972 that every 4-edge–connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge–connected graph has an edge orientation in which every in-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge–connected 5-regular graphs.",

keywords = "3-flow, random graphs, small subgraph conditioning method",

author = "Paweł Prałat and Nick Wormald",

year = "2020",

month = "2",

day = "1",

doi = "10.1002/jgt.22478",

language = "English",

volume = "93",

pages = "147--156",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "John Wiley & Sons",

number = "2",

}

TY - JOUR

T1 - Almost all 5-regular graphs have a 3-flow

AU - Prałat, Paweł

AU - Wormald, Nick

PY - 2020/2/1

Y1 - 2020/2/1

N2 - Tutte conjectured in 1972 that every 4-edge–connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge–connected graph has an edge orientation in which every in-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge–connected 5-regular graphs.

AB - Tutte conjectured in 1972 that every 4-edge–connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge–connected graph has an edge orientation in which every in-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge–connected 5-regular graphs.

KW - 3-flow

KW - random graphs

KW - small subgraph conditioning method

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

U2 - 10.1002/jgt.22478

DO - 10.1002/jgt.22478

M3 - Article

AN - SCOPUS:85075975272

VL - 93

SP - 147

EP - 156

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 2

ER -

Access to Document

10.1002/jgt.22478

Link to publication in Scopus

Research Output