Hypothetical complexity of the nowhere-zero 5-flow problem

DOI<1::AID-JGT1>3.0.CO;2-Q 10.1002/(SICI)1097-0118(199805)28:1<1::AID-JGT1>3.0.CO;2-QzbMath0919.05057OpenAlexW4246798064MaRDI QIDQ4242793

Martin Kochol

Publication date: 11 May 1999

Full work available at URL: https://doi.org/10.1002/(sici)1097-0118(199805)28:1<1::aid-jgt1>3.0.co;2-q

zbMATH Keywords

NP-completenowhere-zero 5-flow

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Superposition and constructions of graphs without nowhere-zero \(k\)-flows ⋮ Tension-flow polynomials on graphs ⋮ Reduction of the 5-flow conjecture to cyclically 6-edge-connected snarks. ⋮ Minimum weakly fundamental cycle bases are hard to find ⋮ Complexity of planar signed graph homomorphisms to cycles ⋮ An equivalent version of the 3-flow conjecture ⋮ Polynomials associated with nowhere-zero flows ⋮ Tension polynomials of graphs

This page was built for publication: Hypothetical complexity of the nowhere-zero 5-flow problem