PulseExploreJournal ClubDebatesTrendingResearchersJournals
Instagram
HomeExploreJournal ClubTrending
Synapse
⌘+K
Synapse
June 13, 2024The Electronic Journal of Combinatorics0 citationsOpen Access

Nowhere-Zero 3-Flows in Signed Planar Graphs

View Full Paper
JLJiaao LiYMYulai MaZMZhengke Miao

Key Points

Key points are not available for this paper at this time.

Abstract

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.

Ask AI
Helpful
Bookmark
Share
View Full Paper

Cite This Study

Li et al. (2024) studied this question.

synapsesocial.com/papers/68e64f79b6db6435875df8edhttps://doi.org/10.37236/11892
Ask AI
Helpful
Bookmark
Share
View Full Paper