A fast distributed algorithm for \((\Delta+1)\)-edge-coloring (Q2664558)

A local algorithm is a distributed algorithm that runs in constant time, which is independent of the size of the network concerned. In this paper, the author proposes a local algorithm to find a proper \((\Delta+1)\)-edge-coloring of a graph of order \(n\) and maximum degree \(\Delta\). In the beginning, he establishes the existence of such an algorithm that computes a \((\Delta+1)\)-edge-coloring of a graph in \(\mathrm{poly}(\Delta, \log n)\) rounds. In order to establish the same, the author uses the distributed approximation algorithm for hypergraph maximum matching and related arguments. Following this, he also explains that there is a connected augmenting subgraph \(H\) of the graph \(G\) under consideration such that \(|E(H)| \le O((\log n)^2)\). In the following section, the notion of happy edges and the process of shifting have been introduced and explained with the help of suitable illustrations. The concepts of hopeful chains and successful chains follow and based on these, some interesting results are proved to establish the relations between these concepts. Later, the author describes a randomized algorithm, namely Multi-Step Vizing Algorithm, to build a happy chain starting with a specified uncolored edge of the graph and perform a probabilistic analysis of this algorithm. The paper is well-written in insightful and logical manner. The style of presentation makes the reading a delightful experience. The author deserves much appreciation for the preparation of such a wonderful paper.