Graph Colouring and Local Algorithms

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

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.