Source-linked AI summary
An 8-flow theorem for signed graphs
Rong Luo, Edita Máčajová, Martin Škoviera, Cun-Quan Zhang
TL;DR
The paper extends a preceding result on signed-graph flows. It proves that flow-admissibility plus a nowhere-zero 4-flow in the underlying graph guarantees a nowhere-zero 8-flow, yielding the planar bridgeless case.
Problem
The paper aims to improve and generalize the preceding Theorem 1.1 result.
Source: §1 · p. 2Method
The proof derives a nowhere-zero Z2 × Z2-flow from the underlying graph’s 4-flow and replaces high-degree vertices with suitable connected balanced subgraphs.
Source: §4 · p. 8Results
A flow-admissible signed graph whose underlying graph admits a nowhere-zero 4-flow admits a nowhere-zero 8-flow.
Source: §1 · p. 2Takeaways & Limitations
Every flow-admissible signed graph with a planar bridgeless underlying graph admits a nowhere-zero 8-flow.
Source: §1 · p. 2The proof reduces to graphs with no degree-2 vertices or positive loops, since flows extend over subdivisions and added positive loops.
Source: §4 · p. 8
Abstract
from arXiv · showhide
We prove that a signed graph admits a nowhere-zero $8$-flow provided that it is flow-admissible and the underlying graph admits a nowhere-zero $4$-flow. When combined with the 4-color theorem, this implies that every flow-admissible bridgeless planar signed graph admits a nowhere-zero $8$-flow. Our result improves and generalizes previous results of Li et al. (European J. Combin. 108 (2023), 103627), which state that every flow-admissible signed $3$-edge-colorable cubic graph admits a nowhere-zero $10$-flow, and that every flow-admissible signed hamiltonian graph admits a nowhere-zero $8$-flow.
1 Introduction
The paper proves that every flow-admissible signed graph whose underlying graph admits a nowhere-zero 4-flow has a nowhere-zero 8-flow. This yields the same 8-flow bound for flow-admissible signed graphs with cubic 3-edge-colorable, planar bridgeless, or hamiltonian underlying graphs.
1 Introduction
- Li et al. showed that a flow-admissible signed graph has a nowhere-zero 10-flow when G is cubic and 3-edge-colorable or planar and bridgeless, and an 8-flow when G is hamiltonian.Source: §1 · p. 2
- A flow-admissible signed graph has a nowhere-zero 8-flow whenever its underlying graph has a nowhere-zero 4-flow.The paper presents this as Theorem 1.2, improving and generalizing Li et al.'s result.Source: §1 · p. 2
- The 8-flow conclusion applies when the underlying graph is cubic and 3-edge-colorable, planar and bridgeless, or hamiltonian.Each class supplies an underlying nowhere-zero 4-flow, so the corollary follows from Theorem 1.2.Source: §1 · p. 2
2 Terminology and notation
This section sets the signed-graph and flow terminology used in the paper. It defines flow-admissibility and gives an equivalent signed-circuit characterization for connected signed graphs.
2 Terminology and notation
- A signed graph assigns each edge a positive or negative sign; a circuit is balanced when it has an even number of negative edges.A signed graph is balanced if it has no unbalanced circuit, and switching preserves the parity of negative edges in every circuit.Source: §2 · pp. 2–3
- An A-flow assigns an abelian-group value to each edge so the signed sum at every vertex is zero; it is nowhere-zero when every edge has a nonzero value.An integer k-flow additionally requires each edge value to have absolute value less than k.Source: §2 · p. 3
- A signed graph is flow-admissible if it has a nowhere-zero integer k-flow for some integer k ≥ 2.For connected signed graphs, this is equivalent to every edge lying in a signed circuit.Source: §2 · pp. 3–4
- A signed circuit is either a balanced circuit or a barbell formed from unbalanced circuits.A barbell consists of two unbalanced circuits meeting at one vertex or connected by a path.Source: §2 · p. 4
3 Lemmas
The lemmas establish how flow-admissibility and nowhere-zero flows behave under contraction of balanced subgraphs, and collect tools used in the main proof. These include flow-extension and characterizations of ordinary graph flows.
3 Lemmas
- Contracting a bridgeless balanced subgraph preserves flow-admissibility in both directions, and every nowhere-zero flow before contraction induces one afterward.The converse is proved using the characterization of flow-admissibility by balanced components after edge deletion.Source: §3 · pp. 4–5
- For a chordless positive circuit with 2 ≤ |δ(V(C))| ≤ 3, a nowhere-zero k-flow after contraction extends to the original signed graph for k ≥ 4.This is the cited extension lemma of Li et al..Source: §3 · p. 5
- A signed graph has a nowhere-zero 2-flow exactly when each component is eulerian and has an even number of negative edges.This is the cited characterization of Xu and Zhang.Source: §3 · p. 5
- A connected signed graph with a Z2-flow whose support has an even number of odd-size components has a 3-flow with the same support on edges valued ±1.This is the cited result of Cheng et al..Source: §3 · p. 5
- When deleting an unbalanced circuit leaves a balanced graph, a flow-admissible signed graph has a 4-flow whose support has the stated degree constraint away from the circuit.The cited lemma of Li et al. states that vertices outside the circuit have degree at most 3 in the support subgraph.Source: §3 · p. 5
- A cubic graph has a nowhere-zero 4-flow exactly when it is 3-edge-colorable; more generally, a graph has a nowhere-zero 4-flow exactly when it has a nowhere-zero Z2 × Z2-flow.These equivalences are stated in the cited lemma of Tutte.Source: §3 · p. 6
4 Proof of Theorem 1.2
The proof establishes an 8-flow for flow-admissible signed graphs whose underlying graph has a nowhere-zero 4-flow, reducing the general case to cubic 3-edge-colorable signed graphs. It also proves the cubic case directly by analyzing the parities of negative edges in the color classes.
Theorem 4.1
- Every flow-admissible signed graph with a cubic, 3-edge-colorable underlying graph admits a nowhere-zero 8-flow, improving Li et al.'s 10-flow bound.The proof constructs an 8-flow in the case that previously required a 10-flow.Source: §4 · p. 6
- When RB contains an unbalanced circuit, parity among the color classes guides flow combinations; switching colors handles mismatched parity cases and yields an 8-flow.When all three classes have matching parity, the proof combines two 3-flows; other cases switch colors on an unbalanced circuit or use further color-pair flows.Source: §4 · pp. 6–7
- When RB has no unbalanced circuit and RY has an even number, flows supported on RB and RY combine to give a nowhere-zero 6-flow.This is one subcase of the cubic proof's construction of an 8-flow.Source: §4 · p. 7
- If the contracted graph contains an unbalanced circuit disjoint from C1, a long barbell supplies a 3-flow that extends to a 4-flow covering RY, which combines with f3 into an 8-flow.Balanced circuits outside the barbell contribute 2-flows used in the extension.Source: §4 · p. 7
- If no such disjoint circuit exists, a 4-flow is extended to cover RY; with at least three unbalanced RY circuits, two color switches and 2-flows also yield an 8-flow.The no-disjoint-circuit case uses the balanced remainder after removing C1; the multiple-circuit case combines f3 with two 2-flows.Source: §4 · pp. 7–8
Proof of Theorem 1.2
- For each vertex of degree at least 4, the proof replaces it with a balanced subgraph while preserving a nowhere-zero Z2 × Z2-flow, then repeats until the graph is cubic.The original graph is recovered by contracting the replacement subgraphs.Source: §4 · pp. 8, 10
- At a replaced vertex, the three incident flow-value counts have the same parity, and the circuit blow-up assigns new values in separate all-odd, partly-zero even, and all-nonzero even cases.The construction checks that the resulting Z2 × Z2-flow remains nowhere-zero.Source: §4 · pp. 8–10
- A flow-admissible signed graph whose underlying graph has a nowhere-zero 4-flow admits a nowhere-zero 8-flow.The proof reduces the graph to a cubic signed graph, applies the cubic result, then contracts the balanced subgraph used in the reduction.Source: §4 · pp. 8, 10