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

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

  • 李佳傲 ,
  • 苏博
展开
  • 南开大学数学科学学院, 天津 300071

收稿日期: 2025-02-26

  网络出版日期: 2025-09-09

基金资助

国家重点研发计划青年科学家项目(2022YFA1006400);国家自然科学基金(12222108);天津市自然科学基金(24JCJQJC00130);天津市自然科学基金(22JCYBJC01520);中央高校基本科研业务费(63253082)

版权

运筹学学报编辑部, 2025, 版权所有,未经授权,不得转载。

Nowhere-zero 5-flows for graphs with bounded genus

  • Jiaao LI ,
  • Bo SU
Expand
  • School of Mathematical Sciences, Nankai University, Tianjin 300071, China
苏博   E-mail: suboll@163.com

Received date: 2025-02-26

  Online published: 2025-09-09

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.

摘要

$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-流[J]. 运筹学学报, 2025 , 29(3) : 124 -134 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.03.006

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.

参考文献

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.
4 TutteW T.On the algebraic theory of graph colourings[J].Journal of Combinatorial Theory,1966,1(1):15-50.
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.
8 SeymourP D.Nowhere-zero 6-flows[J].Journal of Combinatorial Theory, Series B,1981,30(2):130-135.
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.
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.
16 KocholM.Decomposition formulas for the flow polynomial[J].European Journal of Combinatorics,2005,26(7):1086-1093.
17 KocholM.Restrictions on smallest counterexamples to the 5-flow conjecture[J].Combinatorica,2006,26,83-89.
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.
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.
21 SteffenE.Tutte's 5-flow conjecture for highly cyclically connected cubic graphs[J].Discrete Mathematics,2010,310(3):385-389.
22 SteffenE.Tutte's 5-flow conjecture for graphs of nonorientable genus 5[J].Journal of Graph Theory,1996,22(4):309-319.
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.
27 YoungsJ W T.Minimal imbeddings and the genus of a graph[J].Journal of Mathematics and Mechanics,1963,12(2):303-315.
文章导航

/