BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Edita Rollová appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We prove that every 3-edge-connected graph $G$ has a 3-flow $ϕ$ with the property that $|\mathop{supp}(ϕ)| \ge \frac{5}{6} |E(G)|$. The graph $K_4$ demonstrates that this $\frac{5}{6}$ ratio is best possible; there is an infinite family where $\frac 56$ is tight.
We survey known results related to nowhere-zero flows and related topics, such as circuit covers and the structure of circuits of signed graphs. We include an overview of several different definitions of signed graph colouring.
The presented paper studies the flow number $F(G,σ)$ of flow-admissible signed graphs $(G,σ)$ with two negative edges. We restrict our study to cubic graphs, because for each non-cubic signed graph $(G,σ)$ there is a set ${\cal G}(G,σ)$ of cubic graphs such that $F(G, σ) \leq \min \{F(H,σ_H) : (H,σ_H) \in {\cal G}(G)\}$. We prove that $F(G,σ) \leq 6$ if $(G,σ)$ contains a bridge and $F(G,σ) \leq 7$ in general. We prove better bounds, if there is an element $(H,σ_H)$ of ${\cal G}(G,σ)$ which satisfies some additional conditions. In particular, if $H$ is bipartite, then $F(G,σ) \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,σ) \leq 6$. Furthermore, if Tutte's 5-Flow Conjecture is true, then $(G,σ)$ admits a nowhere-zero 6-flow endowed with some strong properties.
Tutte's famous 5-flow conjecture asserts that every bridgeless graph has a nowhere-zero 5-flow. Seymour proved that every such graph has a nowhere-zero 6-flow. Here we give (two versions of) a new proof of Seymour's Theorem. Both are roughly equal to Seymour's in terms of complexity, but they offer an alternative perspective which we hope will be of value.
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.