Nowhere-zero flows in signed series-parallel graphs

DOI10.1137/140994861MaRDI QIDQ2813343zbMATH OpenOpenAlexFDO

Authors Tomáš Kaiser, Edita Rollová

Publication date 23 June 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.1788

zbMATH Keywords

Bouchet conjecturenowhere-zero flowseries-parallel graphsigned graph

Mathematics Subject Classification ID

Flows in graphs (05C21) Signed and weighted graphs (05C22)

Abstract: Bouchet conjectured in 1983 that each signed graph that admits a nowhere-zero flow has a nowhere-zero 6-flow. We prove that the conjecture is true for all signed series-parallel graphs. Unlike the unsigned case, the restriction to series-parallel graphs is nontrivial; in fact, the result is tight for infinitely many graphs.

Recommendations

• Nowhere-zero flows on signed complete and complete bipartite graphs
• Flows on flow-admissible signed graphs
• Nowhere-zero flows on signed wheels and signed fans
• Six-flows on almost balanced signed graphs
• Nowhere-zero 3-flows in signed graphs

Cites work

• A Contribution to the Theory of Chromatic Polynomials
• Circular flow on signed graphs
• Nowhere-zero 3-flows in signed graphs
• Nowhere-zero flows on signed regular graphs
• Nowhere-zero integral flows on a bidirected graph
• Parallel recognition of series-parallel graphs

Cited in

(18)

• Multiple weak 2-linkage and its applications on integer flows of signed graphs
• Nowhere-zero flows on signed wheels and signed fans
• Flow-contractible configurations and group connectivity of signed graphs
• Flows on flow-admissible signed graphs
• The Schrijver system of the flow cone in series-parallel graphs
• Remarks on nowhere-zero flows in signed cubic graphs
• Flow number of signed Halin graphs
• Nowhere-zero flows on signed complete and complete bipartite graphs
• Six-flows on almost balanced signed graphs
• Signed graphs: from modulo flows to integer-valued flows
• Flows on signed graphs without long barbells
• Nowhere zero flows in line graphs
• Nowhere-zero flows on tensor products of signed graphs
• Six-flows of signed graphs with frustration index three
• Signed graphs, nonorientable surfaces, and integer flows
• An 8-flow theorem for signed graphs
• Signed circuit 6-covers of signed K₄-minor-free graphs
• Integral flows on bidirected Eulerian graphs

This page was built for publication: Nowhere-zero flows in signed series-parallel graphs

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