Complementary Graphs with Flows Less Than Three
classification
🧮 math.CO
keywords
deltagraphcomplementaryeitherflowlessresultthen
read the original abstract
X. Hou, H.-J. Lai, P. Li and C.-Q. Zhang [J. Graph Theory 69 (2012) 464-470] showed that for a simple graph $G$ with $|V(G)|\ge 44$, if $\min\{\delta(G),\delta(G^c)\}\ge 4$, then either $G$ or its complementary graph $G^c$ has a nowhere-zero $3$-flow. In this paper, we improve this result by showing that if $|V(G)|\ge 32$ and $\min\{\delta(G),\delta(G^c)\}\ge 4$, then either $G$ or $G^c$ has flow index strictly less than $3$. Our result is proved by a newly developed closure operation and contraction method.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.