1
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

# Towards the Locality of Vizing's Theorem

Preprint

,

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

### Abstract

Vizing showed that it suffices to color the edges of a simple graph using $$\Delta + 1$$ colors, where $$\Delta$$ is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithms are known for obtaining such a coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized $$(\Delta + \tilde{\Theta}(\sqrt{\Delta}))$$-edge-coloring algorithm that runs in $$\text{polylog}(n)$$ rounds by Chang et al. (SODA '18) and the deterministic $$(\Delta + \text{polylog}(n))$$-edge-coloring algorithm that runs in $$\text{poly}(\Delta, \log n)$$ rounds by Ghaffari et al. (STOC '18). We present two distributed edge-coloring algorithms that run in $$\text{poly}(\Delta,\log n)$$ rounds. The first algorithm, with randomization, uses only $$\Delta+2$$ colors. The second algorithm is a deterministic algorithm that uses $$\Delta+ O(\log n/ \log \log n)$$ colors. Our approach is to reduce the distributed edge-coloring problem into an online, restricted version of balls-into-bins problem. If $$\ell$$ is the maximum load of the bins, our algorithm uses $$\Delta + 2\ell - 1$$ colors. We show how to achieve $$\ell = 1$$ with randomization and $$\ell = O(\log n / \log \log n)$$ without randomization.

### Most cited references10

• Record: found

### Locality in Distributed Graph Algorithms

(1992)
Bookmark
• Record: found

### Balls and bins: A study in negative dependence

(1998)
Bookmark
• Record: found

### Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds

Bookmark

### Author and article information

###### Journal
02 January 2019
###### Article
1901.00479