Geodesic
Flows in signed graphs with two negative edges
Edita Rollová1 ; Michael Schubert2 ; Eckhard Steffen2
1University of West Bohemia
2University Paderborn
The electronic journal of combinatorics, Tome 25 (2018) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

The presented paper studies the flow number $F(G,\sigma)$ of flow-admissible signed graphs $(G,\sigma)$ with two negative edges. We restrict our study to cubic graphs, because for each non-cubic signed graph $(G,\sigma)$ there is a set of cubic graphs obtained from $(G,\sigma)$ such that the flow number of $(G,\sigma)$ does not exceed the flow number of any of the cubic graphs. We prove that $F(G,\sigma) \leq 6$ if $(G,\sigma)$ contains a bridge, and $F(G,\sigma) \leq 7$ in general. We prove better bounds, if there is a cubic graph $(H,\sigma_H)$ obtained from $(G,\sigma)$ which satisfies some additional conditions. In particular, if $H$ is bipartite, then $F(G,\sigma) \leq 4$ and the bound is tight. If $H$ is $3$-edge-colorable or critical or if it has a sufficient cyclic edge-connectivity, then $F(G,\sigma) \leq 6$. Furthermore, if Tutte's $5$-Flow Conjecture is true, then $(G,\sigma)$ admits a nowhere-zero $6$-flow endowed with some strong properties.
DOI : 10.37236/4458
Classification : 05C21, 05C22
Mots-clés : flow-admissible signed graphs

Edita Rollová  1   ; Michael Schubert  2   ; Eckhard Steffen  2

1 University of West Bohemia
2 University Paderborn 
@article{10_37236_4458,
     author = {Edita Rollov\'a and Michael Schubert and Eckhard Steffen},
     title = {Flows in signed graphs with two negative edges},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {2},
     doi = {10.37236/4458},
     zbl = {1388.05079},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4458/}
}
TY  - JOUR
AU  - Edita Rollová
AU  - Michael Schubert
AU  - Eckhard Steffen
TI  - Flows in signed graphs with two negative edges
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4458/
DO  - 10.37236/4458
ID  - 10_37236_4458
ER  - 
%0 Journal Article
%A Edita Rollová
%A Michael Schubert
%A Eckhard Steffen
%T Flows in signed graphs with two negative edges
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/4458/
%R 10.37236/4458
%F 10_37236_4458
Edita Rollová; Michael Schubert; Eckhard Steffen. Flows in signed graphs with two negative edges. The electronic journal of combinatorics, Tome 25 (2018) no. 2. doi: 10.37236/4458

Cité par Sources :