Flow extensions and group connectivity with applications

DOI10.1016/J.EJC.2020.103164MaRDI QIDQ2198992zbMATH OpenOpenAlexFDO

Authors Jiaao Li

Publication date 15 September 2020

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.00297

zbMATH Keywords

nowhere-zero flowscircular flownowhere-zero 3-flow

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Flows in graphs (05C21) Connectivity (05C40)

Abstract: We study the flow extension of graphs, i.e., pre-assigning a partial flow on the edges incident to a given vertex and aiming to extend to the entire graph. This is closely related to Tutte's $3$-flow conjecture(1972) that every $4$-edge-connected graph admits a nowhere-zero $3$-flow and a $mathbb{Z}_3$-group connectivity conjecture(3GCC) of Jaeger, Linial, Payan, and Tarsi(1992) that every $5$-edge-connected graph $G$ is $mathbb{Z}_3$-connected. Our main results show that these conjectures are equivalent to their natural flow extension versions and present some applications. The $3$-flow case gives an alternative proof of Kochol's result(2001) that Tutte's $3$-flow conjecture is equivalent to its restriction on $5$-edge-connected graphs and is implied by the 3GCC. It also shows a new fact that Gr{"o}tzsch's theorem (that triangle-free planar graphs are $3$-colorable) is equivalent to its seemly weaker girth five case that planar graphs of grith $5$ are $3$-colorable. Our methods allow to verify 3GCC for graphs with crossing number one, which is in fact reduced to the planar case proved by Richter, Thomassen and Younger(2017). Other equivalent versions of 3GCC and related partial results are obtained as well.

Recommendations

• On group connectivity of graphs
• Two strong 3-flow theorems for planar graphs
• An equivalent version of the 3-flow conjecture
• A note on nowhere-zero 3-flows and \(Z_3\)-connectivity
• Nowhere-zero 3-flows and \(Z_{3}\)-connectivity of a family of graphs

Cites work

• scientific article; zbMATH DE number 3693313 (Why is no real title available?)
• scientific article; zbMATH DE number 4187837 (Why is no real title available?)
• 3-list-coloring planar graphs of girth 5
• A Contribution to the Theory of Chromatic Polynomials
• A Reduction Method for Edge-Connectivity in Graphs
• A short list color proof of Grötzsch's theorem
• An equivalent version of the 3-flow conjecture
• Every planar graph is 5-choosable
• Graph theory
• Group chromatic number of planar graphs of girth at least 4
• Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties
• Group-colouring, group-connectivity, claw-decompositions, and orientations in 5-edge-connected planar graphs
• Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• Nowhere‐zero 3‐flow and ‐connectedness in graphs with four edge‐disjoint spanning trees
• On the algebraic theory of graph colorings
• The weak 3-flow conjecture and the weak circular flow conjecture
• Three-edge-colouring doublecross cubic graphs

Cited in

(4)

• Group-colouring, group-connectivity, claw-decompositions, and orientations in 5-edge-connected planar graphs
• Two strong 3-flow theorems for planar graphs
• Exponentially many nowhere-zero \(\mathbb{Z}_3\)-, \(\mathbb{Z}_4\)-, and \(\mathbb{Z}_6\)-flows
• Flow-continuous mappings -- the influence of the group

This page was built for publication: Flow extensions and group connectivity with applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2198992)