Premium
Hypothetical complexity of the nowhere‐zero 5‐flow problem
Author(s) -
Kochol Martin
Publication year - 1998
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199805)28:1<1::aid-jgt1>3.0.co;2-q
Subject(s) - mathematics , combinatorics , conjecture , cubic graph , zero (linguistics) , graph , flow (mathematics) , discrete mathematics , line graph , voltage graph , geometry , linguistics , philosophy
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