Almost all 5-regular graphs have a 3-flow

Paweł Prałat; Nick Wormald

doi:10.1007/978-3-319-51753-7_15

Almost all 5-regular graphs have a 3-flow

Paweł Prałat, Nick Wormald

School of Mathematics

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

Abstract

Tutte conjectured in 1972 that every 4-edge connected graph has a nowhere-zero 3-flow. This is equivalent to every 5-regular 4-edge-connected graph having an edge orientation in which every out-degree is either 1 or 4. We show that this property holds asymptotically almost surely for random 5-regular graphs.

Original language	English
Pages (from-to)	89-94
Number of pages	6
Journal	Trends in Mathematics
Volume	6
DOIs	https://doi.org/10.1007/978-3-319-51753-7_15
Publication status	Published - 2017

Access to Document

10.1007/978-3-319-51753-7_15

Cite this

@article{7de59dc60ce1400f8747ff1138670a8d,

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 is equivalent to every 5-regular 4-edge-connected graph having an edge orientation in which every out-degree is either 1 or 4. We show that this property holds asymptotically almost surely for random 5-regular graphs.",

author = "Pawe{\l} Pra{\l}at and Nick Wormald",

year = "2017",

doi = "10.1007/978-3-319-51753-7\_15",

language = "English",

volume = "6",

pages = "89--94",

journal = "Trends in Mathematics",

issn = "2297-0215",

publisher = "Springer",

}

TY - JOUR

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

AU - Prałat, Paweł

AU - Wormald, Nick

PY - 2017

Y1 - 2017

N2 - Tutte conjectured in 1972 that every 4-edge connected graph has a nowhere-zero 3-flow. This is equivalent to every 5-regular 4-edge-connected graph having an edge orientation in which every out-degree is either 1 or 4. We show that this property holds asymptotically almost surely for random 5-regular graphs.

AB - Tutte conjectured in 1972 that every 4-edge connected graph has a nowhere-zero 3-flow. This is equivalent to every 5-regular 4-edge-connected graph having an edge orientation in which every out-degree is either 1 or 4. We show that this property holds asymptotically almost surely for random 5-regular graphs.

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

U2 - 10.1007/978-3-319-51753-7_15

DO - 10.1007/978-3-319-51753-7_15

M3 - Article

AN - SCOPUS:85014081567

SN - 2297-0215

VL - 6

SP - 89

EP - 94

JO - Trends in Mathematics

JF - Trends in Mathematics

ER -

Almost all 5-regular graphs have a 3-flow

Abstract

Access to Document

Other files and links

Research output

Almost all 5-regular graphs have a 3-flow

Cite this