Almost all 5‐regular graphs have a 3‐flow. Issue 2 (1st July 2019)

• Record Type: Journal Article
• Authors: Prałat, Paweł; Wormald, Nick
• Is Part Of: Journal of graph theory. Volume 93:Issue 2(2020)
• Page Start: 147
• Page End: 156
• Publication Date: 2019-07-01
• Subjects: 3‐flow -- random graphs -- small subgraph conditioning method; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22478
• Languages: English
• ISSNs: 0364-9024

Abstract

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.