Colorings and Flows

着色和流程

基本信息

  • 批准号:
    RGPIN-2014-06162
  • 负责人:
  • 金额:
    $ 1.09万
  • 依托单位:
  • 依托单位国家:
    加拿大
  • 项目类别:
    Discovery Grants Program - Individual
  • 财政年份:
    2018
  • 资助国家:
    加拿大
  • 起止时间:
    2018-01-01 至 2019-12-31
  • 项目状态:
    已结题

项目摘要

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.
着色和流是图论中两个重要而又有历史意义的子域。平面图的色性一直是研究的一个主要领域。我感兴趣的是证明扩展到更大类图的定理,要么是关于通过对其他图不变量的限制进行图着色的,要么是使用嵌入在拓扑面上的图的自然对偶到顶点着色的流。我的计划是开发结构技术来证明着色或流的存在,或者理解没有所需着色或流的最小图。其动机是为了解决这些领域一些深层次和长期存在的猜测。更具体地说,我的研究将集中在以下几个问题上:**(1)色数、团数和最大度之间的关系:**图着色的一个活跃领域是研究图的三个不变量之间的关系:色数、团数和最大度。事实上,色数有两个平凡的界:由团数给出的下界和由最大次数加1给出的上界。**一个自然的问题是,色数能多接近这些界限。布鲁克斯定理刻画了当色数达到最大度加1的平凡上界时,即当图是完全的或奇圈时。等价地说,如果最大度至少为3,且团数至多为最大度,则色数至多为最大度。我打算研究两个改进布鲁克斯定理的重要猜想。首先是1977年的Borodin-Kostochka猜想,它指出,只要最大度至少为9,团数至多为最大度减1,则色数至多为最大度减1。第二是Reed猜想,色数至多是团数和最大度加1的平均值。**(2)4流猜想。**另一个令人感兴趣的领域是无处可寻的零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猜想将是一个非常重大的突破。此外,我将总结旧的技术并开发新的技术,这些技术可以应用于拓扑图和结构图理论中的其他问题。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Postle, Luke其他文献

Five-list-coloring graphs on surfaces III. One list of size one and one list of size two
表面上的五列表着色图 III.
  • DOI:
    10.1016/j.jctb.2017.06.004
  • 发表时间:
    2018
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Postle, Luke;Thomas, Robin
  • 通讯作者:
    Thomas, Robin

Postle, Luke的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Postle, Luke', 18)}}的其他基金

Graph Theory
图论
  • 批准号:
    CRC-2019-00249
  • 财政年份:
    2022
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Canada Research Chairs
Graph Colouring and Local Algorithms
图着色和局部算法
  • 批准号:
    RGPIN-2019-04304
  • 财政年份:
    2022
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Colouring and Local Algorithms
图着色和局部算法
  • 批准号:
    RGPIN-2019-04304
  • 财政年份:
    2021
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Theory
图论
  • 批准号:
    CRC-2019-00249
  • 财政年份:
    2021
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Canada Research Chairs
Graph Colouring and Local Algorithms
图着色和局部算法
  • 批准号:
    RGPIN-2019-04304
  • 财政年份:
    2020
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Colouring and Local Algorithms
图着色和局部算法
  • 批准号:
    RGPAS-2019-00072
  • 财政年份:
    2020
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Discovery Grants Program - Accelerator Supplements
Graph Theory
图论
  • 批准号:
    1000232868-2019
  • 财政年份:
    2020
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Canada Research Chairs
Graph Colouring and Local Algorithms
图着色和局部算法
  • 批准号:
    RGPIN-2019-04304
  • 财政年份:
    2019
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Discovery Grants Program - Individual
Graph Colouring and Local Algorithms
图着色和局部算法
  • 批准号:
    RGPAS-2019-00072
  • 财政年份:
    2019
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Discovery Grants Program - Accelerator Supplements
Graph Theory
图论
  • 批准号:
    1000230674-2014
  • 财政年份:
    2019
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Canada Research Chairs

相似海外基金

Computing Lagrangian means in multi-timescale fluid flows
计算多时间尺度流体流动中的拉格朗日均值
  • 批准号:
    EP/Y021479/1
  • 财政年份:
    2024
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Research Grant
MHDSSP: Self-sustaining processes and edge states in magnetohydrodynamic flows subject to rotation and shear
MHDSSP:受到旋转和剪切作用的磁流体动力流中的自持过程和边缘状态
  • 批准号:
    EP/Y029194/1
  • 财政年份:
    2024
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Fellowship
Collaborative Research: GEM--Multi-scale Magnetosphere-Ionosphere-Thermosphere Coupling Dynamics Driven by Bursty Bulk Flows
合作研究:GEM——突发体流驱动的多尺度磁层-电离层-热层耦合动力学
  • 批准号:
    2349872
  • 财政年份:
    2024
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Standard Grant
Mesh-free methods for turbulent reacting flows: the next generation of DNS
用于湍流反应流的无网格方法:下一代 DNS
  • 批准号:
    EP/W005247/2
  • 财政年份:
    2024
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Research Grant
SUPERSLUG: Deconstructing sediment superslugs as a legacy of extreme flows
SUPERSLUG:解构沉积物超级段塞作为极端流动的遗产
  • 批准号:
    NE/Z00022X/1
  • 财政年份:
    2024
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Research Grant
Conference: Geometric Flows and Relativity
会议:几何流和相对论
  • 批准号:
    2348273
  • 财政年份:
    2024
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Standard Grant
Conference: St. Louis Topology Conference: Flows and Foliations in 3-Manifolds
会议:圣路易斯拓扑会议:3 流形中的流动和叶理
  • 批准号:
    2350309
  • 财政年份:
    2024
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Standard Grant
CAREER: Turbulence-Resolving Integral Simulations for Boundary Layer Flows
职业:边界层流的湍流求解积分模拟
  • 批准号:
    2340121
  • 财政年份:
    2024
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Continuing Grant
ERI: Experimental Investigation of Compressibility Effects on Turbulent Kinetic Energy Production in Supersonic Flows
ERI:压缩性对超音速流中湍动能产生的影响的实验研究
  • 批准号:
    2347416
  • 财政年份:
    2024
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Standard Grant
Low Regularity and Long Time Dynamics in Nonlinear Dispersive Flows
非线性弥散流中的低规律性和长时间动态
  • 批准号:
    2348908
  • 财政年份:
    2024
  • 资助金额:
    $ 1.09万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了