Colorings and Flows

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

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-apex The 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.