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一致Hypergraph着色结果的本地版本。更广泛的影响。这项拟议的研究为许多最基本的图着色结果开发了本地版本。此外，它引领了图着色的一个全新领域，它有力地概括了最重要的已知结果，同时将图着色的基本范例本身转向网络的局部参数-这是一个非常有用的发展，无论是对于实际应用还是在局部算法的开发中。

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.