亏格有界图的处处非零5-流

doi:10.15960/j.cnki.issn.1007-6093.2025.03.006

摘要/Abstract

摘要： 图$G=(V (G),E (G))$上的一个处处非零$k$-流是指如下定义的一个对$(D,f)$,其中$D$是边集$E (G)$上的一个定向,$f\colon E (G)\to\{\pm1,\pm2,\cdots,\pm (k-1)\}$是边集上的函数,且满足每个顶点的总流出与总流入相等。这一概念由Tutte引入,作为面着色的扩展。Tutte在1954年提出了著名的5-流猜想:每个无桥图都存在处处非零的5-流。尽管该猜想已在一些图类中得到验证,但至今仍未完全解决。本文证明了每个欧拉亏格至多为20的无桥图都存在一个处处非零的5-流,从而改进了若干已知结果。

关键词: 5-流猜想, 最小反例, 亏格有界图

Abstract: A nowhere-zero $k$-flow on a graph $G=(V(G),E(G))$ is a pair $(D,f)$, where $D$ is an orientation on $E(G)$ and $f\colon E(G)\to \{\pm1,\pm2,\cdots,\pm(k-1)\}$ is a function such that the total outflow equals to the total inflow at each vertex. This concept was introduced by Tutte as an extension of face colorings, and Tutte in 1954 conjectured that every bridgeless graph admits a nowhere-zero 5-flow, known as the 5-Flow Conjecture. This conjecture is verified for some graph classes and remains unresolved as of today. In this paper, we show that every bridgeless graph of Euler genus at most 20 admits a nowhere-zero 5-flow, which improves several known results.

Key words: 5-flow conjecture, minimal counterexample, graphs with bounded genus

中图分类号:

O157.5

李佳傲, 苏博. 亏格有界图的处处非零5-流[J]. 运筹学学报（中英文）, 2025, 29(3): 124-134.

LI Jiaao, SU Bo. Nowhere-zero 5-flows for graphs with bounded genus[J]. Operations Research Transactions, 2025, 29(3): 124-134.

参考文献

[1] Appel K, Haken W. Every planar map is four colorable. Part I: Discharging [J]. Illinois Journal of Mathematics, 1977, 21(3): 429-490.
[2] Appel K, Haken W, Koch J. Every planar map is four colorable. Part II: Reducibility [J]. Illinois Journal of Mathematics, 1977, 21(3): 491-567.
[3] Tutte W T. A contribution to the theory of chromatic polynomials [J]. Canadian Journal of Mathematics, 1954, 6: 80-91.
[4] Tutte W T. On the algebraic theory of graph colourings [J]. Journal of Combinatorial Theory, 1966, 1(1): 15-50.
[5] Bondy J, Murty U. Graph Theory with Applications [M]. New York: Elsevier, 1976.
[6] Lai H J, Luo R, Zhang C Q. Integer flows and orientations [M]//Beineke L W, Wilson R J. Topics in Chromatic Graph Theory, Cambridge: Cambridge University Press, 2015: 181-198.
[7] Jaeger F. Flows and generalized coloring theorems in graphs [J]. Journal of Combinatorial Theory, Series B, 1979, 26(2): 205-216.
[8] Seymour P D. Nowhere-zero 6-flows [J]. Journal of Combinatorial Theory, Series B, 1981, 30(2): 130-135.
[9] Fleischner H. Eine gemeinsame basis für die theorie der eulerschen graphen und den Satz von petersen [J]. Monatshefte für Mathematik, 1976, 81: 267-278.
[10] Zhang C Q. Integer Flows and Cycle Covers of Graphs [M]. New York: Marcel Dekker, Inc, 1997.
[11] Jaeger F. Nowhere-zero flow problems [M]//Beineke L W, Wilson R J. Selected Topics in Graph Theory 3, London: Academic Press, 1988: 71-95.
[12] MÖller M, Carstens H G, Brinkmann G. Nowhere-zero flows in low genus graphs [J]. Journal of Graph Theory, 1988, 12(2): 183-190.
[13] Celmins U A. On cubic graphs that do not have an edge 3-coloring [D]. Waterloo: University of Waterloo, 1984.
[14] Jensen T R. Tutte’s k-flow problems [D]. Denmark: Ordense University, 1985.
[15] Kochol M. Reduction of the 5-flow conjecture to cyclically 6-edge-connected snarks [J]. Journal of Combinatorial Theory, Series B, 2004, 90(1): 139-145.
[16] Kochol M. Decomposition formulas for the flow polynomial [J]. European Journal of Combinatorics, 2005, 26(7): 1086-1093.
[17] Kochol M. Restrictions on smallest counterexamples to the 5-flow conjecture [J]. Combinatorica, 2006, 26: 83-89.
[18] Kochol M. Smallest counterexample to the 5-flow conjecture has girth at least eleven [J]. Journal of Combinatorial Theory, Series B, 2010, 100(4): 381-389.
[19] Korcsok P. Minimal counterexamples to flow conjectures [D]. Prague: Charles University, 2015.
[20] Mazzuoccolo G, Steffen E. Nowhere-zero 5-flows on cubic graphs with oddness 4[J]. Journal of Graph Theory, 2017, 85(2): 363-371.
[21] Steffen E. Tutte’s 5-flow conjecture for highly cyclically connected cubic graphs [J]. Discrete Mathematics, 2010, 310(3): 385-389.
[22] Steffen E. Tutte’s 5-flow conjecture for graphs of nonorientable genus 5[J]. Journal of Graph Theory, 1996, 22(4): 309-319.
[23] Erdos P, Sachs H. Regulare graphen gegebener taillenweite mit minimaler knotenzahl [J]. Wissenschaftliche Zeitschrift/Martin-Luther-Universitat, Halle-Wittenberg Mathematischnaturwissenschaftliche Reihe, 1963, 12: 251-257.
[24] Balaban A T. A trivalent graph of girth ten [J]. Journal of Combinatorial Theory, Series B, 1972, 12(1): 1-5.
[25] McKay B, Myrvold W, Nadon J. Fast backtracking principles applied to find new cages [C]//Proccedings of 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998: 188- 191.
[26] Steinberg K. Tutte’s 5-flow conjecture for the projective plane [J]. Journal of Graph Theory, 1984, 8: 277-285.
[27] Youngs J W T. Minimal imbeddings and the genus of a graph [J]. Journal of Mathematics and Mechanics, 1963, 12(2): 303-315.