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

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

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (3): 124-134.doi: 10.15960/j.cnki.issn.1007-6093.2025.03.006

所属专题：第九届中国运筹学会科学技术奖获奖者专辑

• 第九届中国运筹学会科学技术奖获奖者专辑 • 上一篇下一篇

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

李佳傲, 苏博*()

南开大学数学科学学院, 天津 300071

收稿日期:2025-02-26 出版日期:2025-09-15 发布日期:2025-09-09
通讯作者: 苏博 E-mail:suboll@163.com
基金资助:
国家重点研发计划青年科学家项目(2022YFA1006400);国家自然科学基金(12222108);天津市自然科学基金(24JCJQJC00130);天津市自然科学基金(22JCYBJC01520);中央高校基本科研业务费(63253082)

Nowhere-zero 5-flows for graphs with bounded genus

Jiaao LI, Bo SU*()

School of Mathematical Sciences, Nankai University, Tianjin 300071, China

Received:2025-02-26 Online:2025-09-15 Published:2025-09-09
Contact: Bo SU E-mail:suboll@163.com

摘要/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.

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

图/表 1

参考文献 27

1	AppelK,HakenW.Every planar map is four colorable. Part I: Discharging[J].Illinois Journal of Mathematics,1977,21(3):429-490.
2	AppelK,HakenW,KochJ.Every planar map is four colorable. Part Ⅱ: Reducibility[J].Illinois Journal of Mathematics,1977,21(3):491-567.
3	TutteW T.A contribution to the theory of chromatic polynomials[J].Canadian Journal of Mathematics,1954,6,80-91. doi: 10.4153/CJM-1954-010-9
4	TutteW T.On the algebraic theory of graph colourings[J].Journal of Combinatorial Theory,1966,1(1):15-50. doi: 10.1016/S0021-9800(66)80004-2
5	BondyJ,MurtyU.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 RJ. (eds.) Topics in Chromatic Graph Theory, Cambridge: Cambridge University Press, 2015:181-198.
7	JaegerF.Flows and generalized coloring theorems in graphs[J].Journal of Combinatorial Theory, Series B,1979,26(2):205-216. doi: 10.1016/0095-8956(79)90057-1
8	SeymourP D.Nowhere-zero 6-flows[J].Journal of Combinatorial Theory, Series B,1981,30(2):130-135. doi: 10.1016/0095-8956(81)90058-7
9	FleischnerH.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	ZhangC 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. (eds.) Selected Topicsin Graph Theory 3, London: Academic Press, 1988: 71-95.
12	MöllerM,CarstensH G,BrinkmannG.Nowhere-zero flows in low genus graphs[J].Journal of Graph Theory,1988,12(2):183-190. doi: 10.1002/jgt.3190120208
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	KocholM.Reduction of the 5-flow conjecture to cyclically 6-edge-connected snarks[J].Journal of Combinatorial Theory, Series B,2004,90(1):139-145. doi: 10.1016/S0095-8956(03)00080-7
16	KocholM.Decomposition formulas for the flow polynomial[J].European Journal of Combinatorics,2005,26(7):1086-1093. doi: 10.1016/j.ejc.2004.05.004
17	KocholM.Restrictions on smallest counterexamples to the 5-flow conjecture[J].Combinatorica,2006,26,83-89. doi: 10.1007/s00493-006-0006-1
18	KocholM.Smallest counterexample to the 5-flow conjecture has girth at least eleven[J].Journal of Combinatorial Theory, Series B,2010,100(4):381-389. doi: 10.1016/j.jctb.2009.12.001
19	Korcsok P. Minimal counterexamples to flow conjectures[D]. Prague: Charles University, 2015.
20	MazzuoccoloG,SteffenE.Nowhere-zero 5-flows on cubic graphs with oddness 4[J].Journal of Graph Theory,2017,85(2):363-371. doi: 10.1002/jgt.22065
21	SteffenE.Tutte's 5-flow conjecture for highly cyclically connected cubic graphs[J].Discrete Mathematics,2010,310(3):385-389. doi: 10.1016/j.disc.2009.03.014
22	SteffenE.Tutte's 5-flow conjecture for graphs of nonorientable genus 5[J].Journal of Graph Theory,1996,22(4):309-319. doi: 10.1002/(SICI)1097-0118(199608)22:4<309::AID-JGT5>3.0.CO;2-P
23	ErdősP,SachsH.Reguläre graphen gegebener taillenweite mit minimaler knotenzahl[J].Wissenschaftliche Zeitschrift/Martin-Luther-Universit$\ddot{a}$t, Halle-Wittenberg Mathematisch-naturwissenschaftliche Reihe,1963,12,251-257.
24	BalabanA 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	SteinbergK.Tutte's 5-flow conjecture for the projective plane[J].Journal of Graph Theory,1984,8,277-285. doi: 10.1002/jgt.3190080208
27	YoungsJ W T.Minimal imbeddings and the genus of a graph[J].Journal of Mathematics and Mechanics,1963,12(2):303-315.

[1]	杜良丽, 王兵. {C₅, C₆}的平面Turán数[J]. 运筹学学报（中英文）, 2025, 29(2): 221-229.
[2]	吴志伟, 康丽英. 可消去超图p-谱半径的极值问题[J]. 运筹学学报（中英文）, 2025, 29(2): 194-200.
[3]	于明晖. 最大度是3的二部平图的正常多色4-染色[J]. 运筹学学报（中英文）, 2025, 29(2): 95-102.
[4]	齐林明, 赵伟良, 苗连英. 边染色临界图独立数的新下界[J]. 运筹学学报（中英文）, 2025, 29(1): 225-231.
[5]	王朝平, 刘蒙蒙. 积图的Steiner k-hyper Wiener指标[J]. 运筹学学报（中英文）, 2025, 29(1): 216-224.
[6]	孙晓玲, 高玉斌, 杜建伟. 具有固定控制数的树的调和指数[J]. 运筹学学报（中英文）, 2025, 29(1): 207-215.
[7]	杨禹, 朱忠熏, 周鋆鹏. 给定悬挂点数的具有最大无符号拉普拉斯谱半径的k一致超图[J]. 运筹学学报（中英文）, 2025, 29(1): 185-197.
[8]	尚华辉, 苗连英. 关于逆符号全控制数的上界[J]. 运筹学学报（中英文）, 2025, 29(1): 98-104.
[9]	李宝欣, 计省进. 单圈图的零强迫和全强迫[J]. 运筹学学报（中英文）, 2025, 29(1): 198-206.
[10]	谢智红, 郝国亮, 庄蔚. 图的2-彩虹控制数的上下界[J]. 运筹学学报（中英文）, 2024, 28(4): 117-122.
[11]	董清风, 辜振东, 周倩茹, 周书明. 图上粘合运算的Shapley指数[J]. 运筹学学报（中英文）, 2024, 28(4): 123-134.
[12]	胡晓敏, 张淑蓉, 曹婕, 杨卫华. 由完全图对换生成的凯莱图的子结构分析[J]. 运筹学学报（中英文）, 2024, 28(4): 135-142.
[13]	卜月华, 陈雯雯, 朱俊蕾. 不含短圈的平面图的injective边染色[J]. 运筹学学报（中英文）, 2024, 28(4): 143-151.
[14]	陈梓妍, 乔云, 汪毅. 负惯性指数为1的混合图[J]. 运筹学学报（中英文）, 2024, 28(4): 152-161.
[15]	邢抱花, 孙旻昊, 余桂东. 给定独立数的树的倒数度距离[J]. 运筹学学报（中英文）, 2024, 28(2): 143-150.

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

Nowhere-zero 5-flows for graphs with bounded genus

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 27

相关文章 15

编辑推荐

Metrics

本文评价