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 | |
Publication status | Published - 1 Feb 2020 |
Keywords
- 3-flow
- random graphs
- small subgraph conditioning method