Colorings and Flows

点击翻译按钮获取中文摘要

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.