Seminár z teórie grafov - Anna Kompišová (25.10.2018)

vo štvrtok 25.10.2018 o 9:50 hod. v miestnosti M/213

---

Prednášajúci: Anna Kompišová

Názov: Flow and circular flow number of signed cubic graphs

Termín: 25.10.2018, 9:50 hod., M/213

Abstrakt:
A signed graph $(G,\sigma)$ is a graph $G$ with a signature $\sigma \colon E \to \{1,-1\}$. The flow number $\Phi(G,\sigma)$ of a flow-admissible signed graph $(G,\sigma)$ is the smallest integer $k$, for which there exists an integer nowhere-zero $k$-flow on $(G,\sigma)$. The circular flow number $\Phi_c(G,\sigma)$ of a flow-admissible signed graph $(G,\sigma)$ is the infimum of real numbers $r$ for which there exists an $\mathbb{R}$-flow on $(G,\sigma)$ satisfying that absolute values of all the flow values are in the interval $[1,r-1]$.

The relationship between the flow number $\Phi(G)$ and the circular flow number $\Phi_c(G)$ in the unsigned case is simple: $\Phi(G) = \lceil \Phi_c(G)\rceil $. Based on this result Raspaud and Zhu conjectured, that $\Phi(G,\sigma) - \Phi_c(G,\sigma) < 1$ for every flow-admissible signed graph $(G,\sigma)$. This conjecture was disproved using noncubic signed graphs with bridges.

In this talk we disprove the conjecture even for bridgeless signed cubic graphs. We also determine all possible pairs of flow and circular flow number of signed cubic graph if flow number is $3, 4$ or $5$ and prove that every pair is achievable. Finally, we prove that every known signed graph with $\Phi(G,\sigma) = 6$ has also $\Phi_c(G,\sigma) = 6$.

---