|
|||||
|
|
Hypothetical complexity of the nowhere-zero 5-flow problem |
|
| Authors: | Martin Kochol |
| Abstract: | We show that if the well-known 5-Flow Conjecture of Tutte is not true, then the problem to determine whether a (cubic) graph admits a nowhere-zero 5-flow is NP-complete. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 1–11, 1998 |
| Keywords: | nowhere-zero 5-flow NP-completeness |