File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Nowhere-Zero 3-Flows in Signed Graphs

TitleNowhere-Zero 3-Flows in Signed Graphs
Authors
Issue Date2014
PublisherSIAM. The Journal's web site is located at http://www.siam.org/journals/sidma.php
Citation
SIAM Journal on Discrete Mathematics, 2014, v. 28, p. 1628-1637 How to Cite?
AbstractTutte observed that every nowhere-zero $k$-flow on a plane graph gives rise to a $k$-vertex-coloring of its dual, and vice versa. Thus nowhere-zero integer flow and graph coloring can be viewed as dual concepts. Jaeger further shows that if a graph $G$ has a face-$k$-colorable 2-cell embedding in some orientable surface, then it has a nowhere-zero $k$-flow. However, if the surface is nonorientable, then a face-$k$-coloring corresponds to a nowhere-zero $k$-flow in a signed graph arising from $G$. Graphs embedded in orientable surfaces are therefore a special case that the corresponding signs are all positive. In this paper, we prove that if an 8-edge-connected signed graph admits a nowhere-zero integer flow, then it has a nowhere-zero 3-flow. Our result extends Thomassen's 3-flow theorem on 8-edge-connected graphs to the family of all 8-edge-connected signed graphs. And it also improves Zhu's 3-flow theorem on 11-edge-connected signed graphs.
Persistent Identifierhttp://hdl.handle.net/10722/205925

 

DC FieldValueLanguage
dc.contributor.authorWu, Yen_US
dc.contributor.authorYe, Den_US
dc.contributor.authorZang, Wen_US
dc.contributor.authorZhang, C.Qen_US
dc.date.accessioned2014-10-20T09:50:04Z-
dc.date.available2014-10-20T09:50:04Z-
dc.date.issued2014en_US
dc.identifier.citationSIAM Journal on Discrete Mathematics, 2014, v. 28, p. 1628-1637en_US
dc.identifier.urihttp://hdl.handle.net/10722/205925-
dc.description.abstractTutte observed that every nowhere-zero $k$-flow on a plane graph gives rise to a $k$-vertex-coloring of its dual, and vice versa. Thus nowhere-zero integer flow and graph coloring can be viewed as dual concepts. Jaeger further shows that if a graph $G$ has a face-$k$-colorable 2-cell embedding in some orientable surface, then it has a nowhere-zero $k$-flow. However, if the surface is nonorientable, then a face-$k$-coloring corresponds to a nowhere-zero $k$-flow in a signed graph arising from $G$. Graphs embedded in orientable surfaces are therefore a special case that the corresponding signs are all positive. In this paper, we prove that if an 8-edge-connected signed graph admits a nowhere-zero integer flow, then it has a nowhere-zero 3-flow. Our result extends Thomassen's 3-flow theorem on 8-edge-connected graphs to the family of all 8-edge-connected signed graphs. And it also improves Zhu's 3-flow theorem on 11-edge-connected signed graphs.en_US
dc.languageengen_US
dc.publisherSIAM. The Journal's web site is located at http://www.siam.org/journals/sidma.phpen_US
dc.relation.ispartofSIAM Journal on Discrete Mathematicsen_US
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.titleNowhere-Zero 3-Flows in Signed Graphsen_US
dc.typeArticleen_US
dc.identifier.emailZang, W: wzang@maths.hku.hken_US
dc.identifier.authorityZang, W=rp00839en_US
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1137/130941687-
dc.identifier.hkuros241264en_US
dc.identifier.volume28en_US
dc.identifier.spage1628en_US
dc.identifier.epage1637en_US
dc.publisher.placePhiladelphia, USAen_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats