Flow extensions and group connectivity with applications

DOI10.1016/J.EJC.2020.103164zbMATH Open1447.05095arXiv2005.00297OpenAlexW3032608824MaRDI QIDQ2198992FDOQ2198992

Jiaao Li

Publication date: 15 September 2020

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• A Contribution to the Theory of Chromatic Polynomials
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• Every planar graph is 5-choosable
• Three-edge-colouring doublecross cubic graphs
• Title not available (Why is that?)
• A Reduction Method for Edge-Connectivity in Graphs
• On the algebraic theory of graph colorings
• 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
• A short list color proof of Grötzsch's theorem
• 3-list-coloring planar graphs of girth 5
• An equivalent version of the 3-flow conjecture
• The weak 3-flow conjecture and the weak circular flow conjecture
• Title not available (Why is that?)
• Group chromatic number of planar graphs of girth at least 4
• Nowhere‐zero 3‐flow and ‐connectedness in graphs with four edge‐disjoint spanning trees

Cited In (1)

• Exponentially many nowhere-zero \(\mathbb{Z}_3\)-, \(\mathbb{Z}_4\)-, and \(\mathbb{Z}_6\)-flows

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)