Circular flows in planar graphs

DOI10.1137/19M1242513MaRDI QIDQ5216780zbMATH OpenOpenAlexFDO

Authors Daniel W. Cranston, Jiaao Li

Publication date 20 February 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

circular flowmodulo orientationcircular coloringstrongly \({\mathbb Z}_5\) connectedstrongly \({\mathbb Z}_7\) connected

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Flows in graphs (05C21) Connectivity (05C40)

Abstract: For integers $age2b>0$, a emph{circular $a/b$-flow} is a flow that takes values from $pmb,pm(b+1),dots,pm(a-b)$. The Planar Circular Flow Conjecture states that every $2k$-edge-connected planar graph admits a circular $(2+frac2k)$-flow. The cases $k=1$ and $k=2$ are equivalent to the Four Color Theorem and Gr"otzsch's 3-Color Theorem. For $kge3$, the conjecture remains open. Here we make progress when $k=4$ and $k=6$. We prove that (i) {em every 10-edge-connected planar graph admits a circular 5/2-flow} and (ii) {em every 16-edge-connected planar graph admits a circular 7/3-flow.} The dual version of statement (i) on circular coloring was previously proved by Dvov{r}'ak and Postle (Combinatorica 2017), but our proof has the advantages of being much shorter and avoiding the use of computers for case-checking. Further, it has new implications for antisymmetric flows. Statement (ii) is especially interesting because the counterexamples to Jaeger's original Circular Flow Conjecture are 12-edge-connected nonplanar graphs that admit no circular 7/3-flow. Thus, the planarity hypothesis of (ii) is essential.

Recommendations

• Circular chromatic number of planar graphs of large odd girth
• scientific article; zbMATH DE number 3904637
• Circular flows via extended Tutte orientations
• The flow index of regular class I graphs
• Counterexamples to Jaeger's circular flow conjecture

Cites work

• scientific article; zbMATH DE number 4075098 (Why is no real title available?)
• Additive bases and flows in graphs
• Antisymmetric flows and strong colourings of oriented graphs
• Circular \((5,2)\)-coloring of sparse graphs
• Circular flows of nearly Eulerian graphs and vertex-splitting
• Colorings and girth of oriented planar graphs
• Counterexamples to Jaeger's circular flow conjecture
• Density of 5/2-critical graphs
• Edge-Disjoint Spanning Trees of Finite Graphs
• Group Connectivity, Strongly Z_m-Connectivity, and Edge Disjoint Spanning Trees
• Homomorphisms from sparse graphs with large girth.
• Mod (2p + 1)-Orientations and $K_{1,2p+1}$-Decompositions
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• On (k,d)-colorings and fractional nowhere-zero flows
• On strongly \(\mathbb{Z}_{2s + 1}\)-connected graphs
• On the Problem of Decomposing a Graph into n Connected Factors
• On the density of \(C_7\)-critical graphs
• On the maximum average degree and the oriented chromatic number of a graph
• Oriented 5-coloring of sparse plane graphs
• The weak 3-flow conjecture and the weak circular flow conjecture

Cited in

(19)

• Antisymmetric flows on planar graphs
• Construction of graphs with given circular flow numbers
• Some flow-equivalent planar and non-planar graphs
• Circular chromatic number of planar graphs of large odd girth
• scientific article; zbMATH DE number 3904637 (Why is no real title available?)
• The flow index of regular class I graphs
• The Set of Circular Flow Numbers of Regular Graphs
• Density of 3-critical signed graphs
• On the density of \(C_7\)-critical graphs
• Circular coloring and fractional coloring in planar graphs
• Circular flow on signed graphs
• Fractional coloring planar graphs under Steinberg-type conditions
• Signed bipartite circular cliques and a bipartite analogue of Grötzsch's theorem
• Homomorphisms to small negative even cycles
• On circular flows of graphs
• Circular flow number of generalized Blanuša snarks
• scientific article; zbMATH DE number 2129236 (Why is no real title available?)
• Circular flows via extended Tutte orientations
• Boundary-to-Boundary Flows in Planar Graphs

This page was built for publication: Circular flows in planar graphs

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