Colorings and Flows

着色和流是图论中两个重要而又有历史意义的子域。平面图的色性一直是研究的一个主要领域。我感兴趣的是证明扩展到更大类图的定理，要么是关于通过对其他图不变量的限制进行图着色的，要么是使用嵌入在拓扑面上的图的自然对偶到顶点着色的流。我的计划是开发结构技术来证明着色或流的存在，或者理解没有所需着色或流的最小图。其动机是为了解决这些领域一些深层次和长期存在的猜测。(1)图的色数、团数和最大度之间的关系：图着色的一个活跃领域是研究图的三个不变量之间的关系：色数、团数和最大度之间的关系。事实上，色数有两个平凡的界：由团数给出的下界和由最大次数加1给出的上界。一个自然的问题是，色数能多接近这些界限。布鲁克斯定理刻画了当色数达到最大度加1的平凡上界时，即当图是完全的或奇圈时。等价地说，如果最大度至少为3，且团数至多为最大度，则色数至多为最大度。我打算研究两个改进布鲁克斯定理的重要猜想。首先是1977年的Borodin-Kostochka猜想，它指出，只要最大度至少为9，团数至多为最大度减1，则色数至多为最大度减1。第二是Reed猜想，色数至多是团数和最大度加1的平均值。(2)四流猜想。另一个令人感兴趣的领域是无处可寻的零k流的存在。事实上，流提供了一个框架，用于将许多关于顶点着色平面图的定理推广到更一般的图类。例如，Tutte在1966年提出的4流猜想是四色定理的推广。4-流猜想假定，每个没有Petersen图作为次图的无桥图都有一个无处为零的4-流。在20世纪90年代即将发表的一系列论文中，Robertson、Sanders、Seymour和Thomas证明了4流猜想的一个较弱的版本，该猜想指出，每个没有Petersen图作为次图的无桥三次图都有4流，或者在三次图的情况下等价地有3边着色。我的计划是推广他们的策略，以证明4流猜想简化为格罗茨奇的猜想，即顶点图有4流。特别地，下列三个项目是必不可少的：(A)找到至少三个最小度的次极小圈5-连通图(B)为这类图发展一个局部约简规则(C)找到这类图的次极小列表当它们是i)非平面的，ii)非顶点的(1)和(2)中讨论的项目由图着色和图流领域中一些最重要的开放的和长期存在的猜想组成。为图着色猜想提供结构证明将是技术上的一大进步，而将4流猜想简化为Grotzsch猜想将是一个非常重大的突破。此外，我将总结旧的技术并开发新的技术，这些技术可以应用于拓扑图和结构图理论中的其他问题。

Coloring and flows are two important and storied subfields in graph theory. A major area of study has been the chromatic properties of planar graphs. I am interested in proving theorems that extend to larger classes of graphs, either about graph coloring through restrictions on other graph invariants, or, using flows which are the natural dual to vertex coloring for graphs embedded on topological surfaces. My plan is to develop structural techniques to prove the existence of colorings or flows or to understand the minimal graphs which do not have the desired coloring or flow. The motivation is to solve a number of deep and long-standing conjectures in these areas. More specifically, my research will focus on the following problems:(1) Relationship between the chromatic number, clique number and maximum degree:One active area of graph coloring is the study of the relationship between three graph invariants: the chromatic number, the clique number and the maximum degree. In fact, there are two trivial bounds on the chromatic number: a lower bound given by the clique number and an upper bound given by the maximum degree plus one. A natural question is how close can the chromatic number come to attaining these bounds. Brooks' Theorem characterizes when the chromatic number achieves the trivial upper bound of the maximum degree plus one, namely when the graph is complete or an odd cycle. Equivalently, this says that if the maximum degree is at least three and the clique number is at most the maximum degree, then the chromatic number is at most the maximum degree. I plan to investigate two important conjectures which improve upon Brooks' Theorem. First is the Borodin-Kostochka Conjecture from 1977, which states that the chromatic number is at most the maximum degree minus one as long as maximum degree is at least nine and the clique number is at most maximum degree minus one. Second is Reed's conjecture that the chromatic number is at most the average of the clique number and maximum degree plus one. (2) 4-Flow Conjecture. Another area of interest is the existence of nowhere-zero k-flows. Indeed, flows provide a framework for generalizing many theorems about vertex-coloring planar graphs to more general classes of graphs. For example, the 4-flow conjecture, conjectured by Tutte in 1966, is a generalization of the Four Color Theorem. The 4-flow conjecture posits that every bridgeless graph without the Petersen graph as a minor has a nowhere-zero 4-flow. In a series of soon-to-be published papers dating from the 1990s, Robertson, Sanders, Seymour and Thomas proved a weaker version of the 4-flow conjecture which states that every bridgeless cubic graph without the Petersen graph as a minor has a 4-flow, or equivalently in the case of cubic graphs, a 3-edge-coloring. My plan is to generalize their strategy to show that the 4-flow conjecture reduces to Grotzsch's conjecture that apex graphs have a 4-flow. In particular, the following three projects are essential:(a) Finding the minor-minimal cyclically 5-connected graphs of minimum degree at least three(b) Developing a local reduction rule for such graphs(c) Finding the minor-minimal lists of such graphs when they are i) non-planar, ii) non-apexThe projects discussed in (1) and (2) consist of some of the most important open and long-standing conjectures in the areas of graph coloring and graph flows. Providing structural proofs for the graph coloring conjectures will be a major advance in technique while reducing the 4-flow conjecture to Grotzsch's conjecture would be a very significant breakthrough. Furthermore, I will generalize older techniques and develop new ones that can be applied to other problems in topological and structural graph theory.