Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2008-009 (August 13, 2008)

All 4-Edge-Connected HHD-Free Graphs are Z_3-Connected
by Takuro Fukunaga

pdf File


An undirected graph $G=(V,E)$ is called $Z_3$-connected if for all $b: V \rightarrow Z_3$ with $\sum_{v \in V}b(v)=0$, an orientation $D=(V,A)$ of $G$ has a $Z_3$-valued nowhere-zero flow $f: A \rightarrow Z_3-\{0\}$ such that $\sum_{e \in \delta^+(v)}f(e)-\sum_{e \in \delta^-(v)}f(e)=b(v)$ for all $v \in V$. We show that all 4-edge-connected HHD-free graphs are $Z_3$-connected. This extends the result due to Lai (2000), which proves the fact for chordal graphs.