Colorings and Flows

染色与流是图论中两个重要的研究领域。一个主要的研究领域是平面图的色性。我有兴趣证明定理，扩大到更大的类的图形，无论是关于图着色通过限制其他图形不变量，或者，使用流是自然对偶顶点着色的图形嵌入拓扑表面。我的计划是开发结构技术来证明着色或流的存在，或者理解不具有所需着色或流的最小图。其动机是解决这些领域中一些深刻而长期存在的问题。更具体地说，我的研究将集中在以下问题上： (1)色数、团数和最大度之间的关系： 图着色的一个活跃领域是研究图的色数、团数和最大度这三个不变量之间的关系。实际上，色数有两个平凡的界：一个由团数给出的下界和一个由最大度加1给出的上界。 一个很自然的问题是，色数能有多接近这些界限。布鲁克斯定理刻画了当图的色数达到最大度加1的平凡上界时，即当图是完全图或奇圈时。等价地说，如果最大次数至少是3，而团数至多是最大次数，那么色数至多是最大次数。我计划研究两个重要的定理，它们改进了布鲁克斯定理。第一个是1977年的Borodin-Kostochka猜想，它指出色数至多是最大度减1，只要最大度至少是9，团数至多是最大度减1。第二个是Reed猜想，色数至多是团数和最大度加1的平均值。 (2)四流猜想 另一个感兴趣的领域是无处零k流的存在。事实上，流提供了一个框架，推广许多定理顶点着色平面图更一般的类的图。例如，Tutte在1966年提出的4流猜想是四色定理的推广。4-流猜想假定每个没有Petersen图作为子图的无桥图都有一个无处为零的4-流。 在1990年代的一系列即将发表的论文中，Robertson，Sanders，Seymour和托马斯证明了4-flow猜想的一个较弱版本，该猜想指出每个没有Petersen图作为子图的无桥三次图都有4-flow，或者等价地，在三次图的情况下，有3-边染色。我的计划是推广他们的策略，以表明4流猜想减少到Grotzsch的猜想，顶点图有一个4流。 特别是，以下三个项目至关重要： (a)求最小度至少为3的次-极小循环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-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.