有关图的处处非零3-流的研究

This project mainly studies the problems in graph theory: the integer flow problems due to four-color conjecture. In 1954, Tutte introduced the concept of nowhere-zero flows as a tool to attack the four-color conjecture. Moreover, Tutte proposed the well-known 3-flow conjecture: every 4-edge-connected graph admits a nowhere-zero 3-flow. With contraction, vertex-splitting, induction and contradiction method, we mainly study two aspects of problems around 3-flow conjecture: (1) study certain conditions for nowhere-zero 3-flows; (2) study nowhere-zero 3-flows in claw-free graphs with the structure: every edge lies in a 3-circuit. Problem (1) studies the existence of nowhere-zero 3-flows in graphs for the first time by using of the relationship between the connectivity and independent number. Problem (2) explores sufficient and necessary condition of nowhere-zero 3-flows in graphs which do not contain forbidden subgraph-claw.

本项目主要研究图论中的典型问题：源于四色猜想的整数流问题。1954年，Tutte 在研究四色问题时引入了整数流的概念，并提出了著名的3-流猜想：每个4-边连通图存在处处非零3-流。围绕此猜想，我们拟采用收缩法，点分裂法，归纳法以及反证法来研究以下两个方面的问题：（1）满足 Chvatal-Erdos 条件的图的处处非零3-流。（2）每条边都包含在3-圈中的无爪图的处处非零3-流。问题（1）第一次利用点连通度与独立点数之间的关系研究处处非零3-流的存在性问题（2）旨在探索不含禁用子图爪这一类图存在处处非零3-流的充分必要条件。