NOWHERE-ZERO FLOWS IN SIGNED SERIES-PARALLEL GRAPHS

被引：12

作者：

Kaiser, Tomas ^{[1
,2
,3
]}

Rollova, Edita ^{[1
,2
]}

机构：

[1] Univ West Bohemia, Dept Math, Univ 8, Plzen 30614, Czech Republic

[2] Univ West Bohemia, European Ctr Excellence NTIS New Technol Informat, Univ 8, Plzen 30614, Czech Republic

[3] Inst Theoret Comp Sci CE ITI, Prague, Czech Republic

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 2016年 / 30卷 / 02期

关键词：

signed graph; series-parallel graph; nowhere-zero flow; Bouchet's conjecture;

D O I：

10.1137/140994861

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：1248 / 1258

页数：11

共 8 条

[1]

[Anonymous], 1987, THESIS

[2] NOWHERE ZERO INTEGRAL FLOWS ON A BIDIRECTED GRAPH [J].