报告题目：Cycle Covers and Flows

报告人：范更华教授

报告时间：7月25日下午15:30

报告摘要：A cycle is a graph in which each vertex is incident with an even number of edges. A cycle cover of a graph $G$ is a collection of cycles such that each edge of $G$ is in at least one of the cycles. A $k$-flow in a graph $G$ with an orientation is a function $f$ from the edge set of $G$ to an abelian group of order $k$ such that at each vertex $v$, the sum of $f(e)$

over all the edges entering $v$ is equal to the sum of $f(e)$ over all the edges leaving $v$. A $k$-flow $f$ is called nowhere-zero if $f(e)\not= 0$ for every edge $e$. It is known that a graph has a nowhere-zero $2^t$-flow if and only if it has a cycle cover consisting of $t$ cycles. For a plane graph, the existence of a nowhere-zero $k$-flow is equivalent to a $k$-face coloring. Thus,

the famous Four-Color-Theorem is equivalent to the existence of a nowhere-zero $4$-flow, and also equivalent to the existence of a cycle cover consisting of two cycles. The length of a cycle cover is the sum of the lengths of the cycles in the cover. It was conjectured that every bridgeless graph with $m$ edges has a cycle cover of length at most ${7\over 5}m$. The truth of this conjecture would implies the truth of the well-known Cycle Double Cover Conjecture: every bridgeless graph has a collection of cycles such that each edge is in precisely two of the cycles. Recently we obtained results on 4-flows, which was used to improve the existing results on the lengths of cycle covers.

范更华教授简介：福州大学副校长，教授，博士生导师。离散数学及其应用教育部重点实验室主任。1996年度中国科学院“百人计划”入选者；1998年度国家杰出青年科学基金获得者；获2005年度国家自然科学奖二等奖（独立获奖）。范更华主要从事图论基础理论及其应用的研究。他的一个成果以“范定理”、“范条件”被国内外同行广泛引用。一些成果作为定理出现在国外的教科书中。范更华先后四次主持国家自然科学基金委重点项目；连续两次负责国家重点基础研究发展计划（973计划）课题。目前担任多份国内外期刊编委；1997至今，一直担任国际图论界权威刊物《图论杂志》（Journal of Graph Theory）的执行编委（Managing Editor）。