期刊
SIAM JOURNAL ON DISCRETE MATHEMATICS
卷 34, 期 1, 页码 497-519出版社
SIAM PUBLICATIONS
DOI: 10.1137/19M1242513
关键词
circular flow; circular coloring; planar; modulo orientation; strongly Z(5) connected; strongly Z(7) connected
资金
- NSA [H98230-15-1-0013]
- National Natural Science Foundation of China [11901318]
For integers a >= 2b > 0, a circular a/b-flow is a flow that takes values from {+b, +/-(b+ 1), ..., +/-(a - b)}. The Planar Circular Flow Conjecture states that every 2k-edge-connected planar graph admits a circular (2 + 2/k)-flow. The cases k = 1 and k = 2 are equivalent to the Four Color Theorem and Grotzsch's 3-Color Theorem. For k >= 3, the conjecture remains open. Here we make progress when k = 4 and k = 6. We prove that (i) every 10-edge-connected planar graph admits a circular 5/2-flow and (ii) every 16-edge-connected planar graph admits a circular 7/3flow. The dual version of statement (i) on circular coloring was previously proved by Dvorak and Postle [Combinatorica, 37 (2017), pp. 863-886], 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据