File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/130941687
- Scopus: eid_2-s2.0-84907994054
- WOS: WOS:000343230800034
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Nowhere-Zero 3-Flows in Signed Graphs
Title | Nowhere-Zero 3-Flows in Signed Graphs |
---|---|
Authors | |
Keywords | Integer flow Modulo orientation Signed graph |
Issue Date | 2014 |
Publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php |
Citation | SIAM Journal on Discrete Mathematics, 2014, v. 28 n. 3, p. 1628-1637 How to Cite? |
Abstract | Tutte 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 Identifier | http://hdl.handle.net/10722/205925 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 1.031 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Wu, Y | en_US |
dc.contributor.author | Ye, D | en_US |
dc.contributor.author | Zang, W | en_US |
dc.contributor.author | Zhang, C.Q | en_US |
dc.date.accessioned | 2014-10-20T09:50:04Z | - |
dc.date.available | 2014-10-20T09:50:04Z | - |
dc.date.issued | 2014 | en_US |
dc.identifier.citation | SIAM Journal on Discrete Mathematics, 2014, v. 28 n. 3, p. 1628-1637 | en_US |
dc.identifier.issn | 0895-4801 | - |
dc.identifier.uri | http://hdl.handle.net/10722/205925 | - |
dc.description.abstract | Tutte 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.language | eng | en_US |
dc.publisher | Society for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php | - |
dc.relation.ispartof | SIAM Journal on Discrete Mathematics | en_US |
dc.rights | © 2014 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Discrete Mathematics in volume 28, issue 3, published by the Society for Industrial and Applied Mathematics (SIAM). | - |
dc.subject | Integer flow | - |
dc.subject | Modulo orientation | - |
dc.subject | Signed graph | - |
dc.title | Nowhere-Zero 3-Flows in Signed Graphs | en_US |
dc.type | Article | en_US |
dc.identifier.email | Zang, W: wzang@maths.hku.hk | en_US |
dc.identifier.authority | Zang, W=rp00839 | en_US |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.1137/130941687 | - |
dc.identifier.scopus | eid_2-s2.0-84907994054 | - |
dc.identifier.hkuros | 241264 | en_US |
dc.identifier.volume | 28 | en_US |
dc.identifier.issue | 3 | - |
dc.identifier.spage | 1628 | en_US |
dc.identifier.epage | 1637 | en_US |
dc.identifier.isi | WOS:000343230800034 | - |
dc.publisher.place | Philadelphia, USA | en_US |
dc.identifier.issnl | 0895-4801 | - |