Graph Colouring and 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.