Hypothetical complexity of the nowhere-zero 5-flow problem

DOI10.1002/(SICI)1097-0118(199805)28:1%3C1::AID-JGT1%3E3.0.CO;2-QMaRDI QIDQ4242793zbMATH OpenOpenAlexFDO

Authors Martin Kochol

Publication date 11 May 1999

Full work available at URL https://doi.org/10.1002/(sici)1097-0118(199805)28:1%3C1::aid-jgt1%3E3.0.co;2-q

zbMATH Keywords

nowhere-zero 5-flowNP-complete

Mathematics Subject Classification ID

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

Cited in

(9)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4242793)