Nowhere-Zero 3-Flows in Signed Planar Graphs

• DOI: 10.37236/11892
• Publication Date: 2024-06-13T16:38:31Z
• Authors: Jiaao Li; Yulai Ma; Zhengke Miao; Yongtang Shi; Weifan Wang
• Keywords: 0102 computer and information sciences; 01 natural sciences

Extending Grötzsch's 3-coloring theorem in the flow setting, Steinberg and Younger in 1989 proved that every 4-edge-connected planar or projective planar graph admits a nowhere-zero 3-flow (3-NZF for short), while Tutte's 3-flow conjecture asserts all 4-edge-connected graphs admit 3-NZFs. In this paper, we generalize Grötzsch's theorem to signed planar graphs by showing that every 4-edge-connected signed planar graph with two negative edges admits a 3-NZF. On the other hand, a result from Máčajová and Škoviera implies that there exist infinitely many 4-edge-connected signed planar graphs with three negative edges admitting no 3-NZFs but permitting 4-NZFs. Our proof employs the flow extension ideas from Steinberg-Younger and Thomassen, as well as refined exploration of the location of negative edges and elaborated discharging arguments in signed planar graphs.