Circular Flows and Orientations of Signed Graphs
报告题目(Title)：Circular Flows and Orientations of Signed Graphs
报告人(Speaker)：李佳傲博士 (南开大学)
地点(Place)：后主楼1129报告厅
时间(Time)：2019年11月25日 16：00-17：00
邀请人(Inviter)：徐敏
报告摘要
A flow in a (signed) graph is an orientation and an edge-weighting such net-inflow equals net-outflow. There are several equivalent definitions of circular $(2+\frac{1}{p})$-flow in graphs: (A) $G$ admits a mod $(2p+1)$-orientation, an orientation such that the indegree is congruent to outdegree at each vertex mod $2p+1$, (B) $G$ admits an integer-valued $(2+\frac{1}{p})$-flow, a flow taking values $\pm p, \pm (p+1)$ only, (C) $G$ admits a real-valued $(2+\frac{1}{p})$-flow, a flow taking values in interval union $[-p-1,-p]\cup[p,p+1]$. It is known that (A),(B),(C) are all not equivalent for signed graphs, and (A) and (C), (B) and (C) are not equivalent even for bridgeless signed graphs. In this talk, we show that (A) and (B) are equivalent for all bridgeless signed graphs, generalizing some previous results. Raspaud and Zhu (2011) asked for signed graphs whether real-valued $(k,d)$-flows imply nowhere-zero integer $\lceil k/d\rceil$-flows, but negatively answered by some counterexamples, and moreover when $p=1$ (C) does not imply a nowhere-zero integer $3$-flow for some bridgeless signed graphs. We show a positive partial result that when $p\ge 3$, (B) (or (A)) implies nowhere-zero integer $3$-flows for all bridgeless signed graphs.
