Graph Colouring and Local Algorithms

图着色和局部算法

• 批准号: RGPIN-2019-04304
• 负责人: Postle, Luke
• 金额: $ 3.5万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=714766
• 关键词: Graph; Colouring; Local; Algorithms

Local Algorithms for Graph Colouring The main areas of this proposed research program are two-fold: 1) to develop local algorithms for some of the most important problems in graph colouring, and 2) to develop local versions of the most prominent graph colouring theorems wherein the parameters (e.g. degree, colours) are local to the vertices. 1. Algorithms and Local Algorithms for Colouring Graphs Finding efficient polynomial-time algorithms for colouring graphs is a fundamental problem, both for its theoretical implications and practical heuristics. Graph colouring is a useful model for many applications in information and communication technologies such as server processing, frequency allocation, scheduling and distributed algorithms. While substantial progress has been made in recent decades on improved bounds for the number of colours needed in these problems, there are still many recent important results that lack algorithms. Moreover, even those problems that have admitted algorithms lack efficient local algorithms, which are essential for use in distributed computing. Objectives. 1.1 Develop Local Algorithms for Colouring Graphs on Surfaces. 1.2 Develop Algorithms for Potential Method. 1.3 Develop Local Algorithms for Colouring Graphs with given Clique Number. Broader Impact. The proposed research develops local algorithms for some of the most important graphs colourings problems in a variety of areas from planar graphs and sparse graphs to graphs of given clique number. The research uses newly developed techniques like hyperbolic families and correspondence colourings to develop a theory of local graph colouring algorithms and will have a major impact on both of those fields. 2. Local Versions of Colouring Theorems We further propose developing local versions of the results themselves. Creating local versions is a new paradigm for graph colouring that I have taken a leading role in [CCV J5, J13]. Such versions are both far-reaching generalizations of previous results while simultaneously holding much potential for applications. Since most graph colouring results bound the number of colours needed in terms of parameters of a graph, a local version of a graph colouring result then is one where the parameters (including number of colours) are localized to the vertices. Objectives. 2.1 Develop Better Bounds for Reed's Conjecture and its Local Version. 2.2 Develop Local Versions for Edge Colouring Results. 2.3 Develop Local Versions for k-uniform Hypergraph Colouring Results. Broader Impact. The proposed research develops local versions for many of the most fundamental graph colouring results. Furthermore, it spearheads an entirely new area of graph colouring which strongly generalizes the most important known results while shifting the underlying paradigm of graph colouring itself toward the local parameters of networks a very useful development both for practical applications and in the development of local algorithms.

图着色的局部算法 该研究计划的主要领域有两个方面：1）为图着色中一些最重要的问题开发局部算法，2）开发最突出的图着色定理的局部版本，其中参数（例如度，颜色）是顶点的局部。 1.图的着色算法和局部算法 寻找有效的多项式时间图着色算法是一个基本的问题，无论是其理论意义和实用算法。图着色是信息和通信技术中许多应用的有用模型，例如服务器处理、频率分配、调度和分布式算法。虽然近几十年来在这些问题中所需的颜色数量的改进界限方面取得了实质性进展，但仍然有许多最近的重要结果缺乏算法。此外，即使是那些问题，承认算法缺乏有效的本地算法，这是必不可少的分布式计算中使用。 目标. 1.1开发局部算法为表面上的着色图。 1.2开发势方法的算法。 1.3给出了给定团数的图着色的局部算法。 更广泛的影响。该研究开发了一些最重要的图形着色问题在各种领域的局部算法，从平面图和稀疏图的图给定的团数。该研究使用新开发的技术，如双曲族和对应着色，以开发局部图着色算法的理论，并将对这两个领域产生重大影响。 2.着色定理的局部形式 我们进一步建议开发本地版本的结果本身。创建本地版本是一种新的图形着色范例，我在[CCV J5，J13]中发挥了主导作用。这些版本都是对以前结果的深远概括，同时具有很大的应用潜力。由于大多数图着色结果限制了图的参数所需的颜色数量，因此图着色结果的局部版本是其中参数（包括颜色数量）被局部化到顶点的版本。 目标. 2.1为里德猜想及其局部版本提供更好的界。 2.2为边缘着色结果开发本地版本。 2.3为k-均匀超图着色结果开发本地版本。 更广泛的影响。拟议的研究开发本地版本的许多最基本的图形着色结果。此外，它开创了一个全新的领域的图形着色，强烈概括了最重要的已知结果，而转移的基本范式的图形着色本身对本地参数的网络一个非常有用的发展，无论是在实际应用中，并在当地的算法的发展。