Circular flows in planar graphs

DOI10.1137/19M1242513zbMATH Open1433.05137arXiv1812.09833OpenAlexW3008794855MaRDI QIDQ5216780FDOQ5216780

Authors: Daniel W. Cranston, Jiaao Li 

Publication date: 20 February 2020

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

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• The flow index of regular class I graphs
• Density of 3-critical signed graphs
• The Set of Circular Flow Numbers of Regular Graphs
• Circular coloring and fractional coloring in planar graphs
• On the density of \(C_7\)-critical graphs
• Fractional coloring planar graphs under Steinberg-type conditions
• Circular flow on signed graphs
• 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
• Title not available (Why is that?)
• 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)