Circular flows in mono-directed signed graphs

Jiaao Li , Reza Naserasr (1) , Zhouningxin Wang , Xuding Zhu

1 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale

In this paper the concept of circular r-flows in a mono-directed signed graph (G, σ) is introduced. That is a pair (D, f), where D is an orientation on G and f : E(G) → (−r, r) satisfies that |f (e)| ∈ [1, r − 1] for each positive edge e and |f (e)| ∈ [0, r 2 − 1] ∪ [ r 2 + 1, r) for each negative edge e, and the total inflow equals the total out-flow at each vertex. The circular flow index of a signed graph (G, σ) with no positive bridge, denoted Φ c (G, σ), is the minimum r such that (G, σ) admits a circular r-flow. This is the dual notion of circular colorings and circular chromatic numbers of signed graphs recently introduced in [Circular chromatic number of signed graphs. R. Naserasr, Z. Wang, and X. Zhu. Electronic Journal of Combinatorics, 28(2)(2021), #P2.44], and is distinct from the concept of circular flows in bi-directed graphs associated to signed graphs studied in the literature. We give several equivalent definitions, study basic properties of circular flows in mono-directed signed graphs, and explore relations with flows in graphs. Then we focus on upper bounds on Φ c (G, σ) in terms of the edge-connectivity of G. Tutte's 5-flow conjecture is equivalent to saying that every 2-edge-connected signed graph has circular flow index at most 10. We show that if (G, σ) is a 3-edge-connected (4-edge-connected, respectively) signed graph, then Φ c (G, σ) ≤ 6 (Φ c (G, σ) ≤ 4, respectively). For k ≥ 2, if (G, σ) is (3k − 1)-edge-connected, then Φ c (G, σ) ≤ 2k k−1 ; if (G, σ) is 3k-edge-connected, then Φ c (G, σ) < 2k k−1 ; and if (G, σ) is (3k + 1)-edge-connected, then Φ c (G, σ) ≤ 4k+2 2k−1. When restricted to the class of signed Eulerian graphs, if (G, σ) is (6k − 2)-edgeconnected, then Φ c (G, σ) ≤ 4k 2k−1. Applying this on planar graphs we conclude that every signed bipartite planar graph of negative-girth at least 6k − 2 admits a homomorphism to C −2k. For the particular values of r k = 2k k−1 , and when restricted to two natural subclasses of signed graphs, the existence of a circular r k-flow is strongly connected with the existence of a modulo k-orientation, and in case of planar graphs, based on duality, with the homomorphisms to C −k .

Domaines: Mathématique discrète [cs.DM]

Jiaao Li, Reza Naserasr, Zhouningxin Wang, Xuding Zhu. Circular flows in mono-directed signed graphs. 2022. ⟨hal-03840742⟩