Name
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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1002/jgt.22478 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
3-flow,random graphs,small subgraph conditioning method | Topology,Random regular graph,Discrete mathematics,Combinatorics,Indifference graph,Forbidden graph characterization,Chordal graph,Nowhere-zero flow,1-planar graph,Universal graph,Mathematics,Planar graph | Journal |
Volume | Issue | ISSN |
93.0 | 2.0 | 0364-9024 |
Citations | PageRank | References |
2 | 0.49 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pawel Pralat | 1 | 234 | 48.16 |
| Nicholas C. Wormald | 2 | 1506 | 230.43 |