✦ LIBER ✦

Extending a partial nowhere-zero 4-flow

✍ Scribed by Lai, Hong-Jian

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 124 KB
Volume: 30
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199904)30:4<277::aid-jgt3>3.0.co;2-d

No coin nor oath required. For personal study only.

✦ Synopsis

In [J Combin Theory Ser B, 26 (1979), 205-216]

, Jaeger showed that every graph with 2 edge-disjoint spanning trees admits a nowhere-zero 4-flow. In [J Combin Theory Ser B, 56 (1992), 165-182], Jaeger et al. extended this result by showing that, if A is an abelian group with |A| = 4, then every graph with 2 edgedisjoint spanning trees is A-connected. As graphs with 2 edge-disjoint spanning trees are all collapsible, we in this note improve the latter result by showing that, if A is an abelian group with |A| = 4, then every collapsible graph is A-connected. This allows us to prove the following generalization of Jaeger's theorem: Let G be a graph with 2 edge-disjoint spanning trees and let M be an edge cut of G with |M | ≤ 4. Then either any partial nowhere-zero 4-flow on M can be extended to a nowhere-zero 4-flow of the whole graph G, or G can be contracted to one of three configurations, including the wheel of 5 vertices, in which cases certain partial nowhere-zero 4-flows on M cannot be extended. Our results also improve

📜 SIMILAR VOLUMES

Nowhere zero 4-flow in regular matroids

✍ Hong-Jian Lai; Xiangwen Li; Hoifung Poon 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 96 KB

## Abstract Jensen and Toft 8 conjectured that every 2‐edge‐connected graph without a __K__~5~‐minor has a nowhere zero 4‐flow. Walton and Welsh 19 proved that if a coloopless regular matroid __M__ does not have a minor in {__M__(__K__~3,3~), M\*(__K__~5~)}, then __M__ admits a nowhere zero 4‐flow.

Cycle covers of graphs with a nowhere-ze

Cycle covers of graphs with a nowhere-zero 4-flow

✍ André Raspaud 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 234 KB 👁 1 views

## Abstract It is shown that the edges of a simple graph with a nowhere‐zero 4‐flow can be covered with cycles such that the sum of the lengths of the cycles is at most |__E__(__G__)| + |__V__(__G__)| −3. This solves a conjecture proposed by G. Fan.

The size of graphs without nowhere-zero

The size of graphs without nowhere-zero 4-flows

✍ Hong-Jian Lai 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 428 KB 👁 1 views

Let G be a 2-edge-connected simple graph with order n. We show that if IV(G)l 5 17, then either G has a nowhere-zero 4-flow, or G is contractible to the Petersen graph. We also show that for n large, if I€(G)J L (' 2 17) + 34, then either G has a nonwhere-zero 4-flow, or G can be contracted to the P