## Abstract

We give a randomized ∆-coloring algorithm in the LOCAL model that runs in poly log log n rounds, where n is the number of nodes of the input graph and ∆ is its maximum degree. This means that randomized ∆-coloring is a rare distributed coloring problem with an upper and lower bound in the same ballpark, poly log log n, given the known Ω(log_{∆} log n) lower bound [Brandt et al., STOC'16]. Our main technical contribution is a constant time reduction to a constant number of (deg + 1)-list coloring instances, for ∆ = ω(log^{4} n), resulting in a poly log log n-round CONGEST algorithm for such graphs. This reduction is of independent interest for other settings, including providing a new proof of Brooks' theorem for high degree graphs, and leading to a constant-round Congested Clique algorithm in such graphs. When ∆ = Ω(log^{22} n), our algorithm even runs in O(log^{∗} n) rounds, showing that the base in the Ω(log_{∆} log n) lower bound is unavoidable. Previously, the best LOCAL algorithm for all considered settings used a logarithmic number of rounds. Our result is the first CONGEST algorithm for ∆-coloring non-constant degree graphs.

Original language | English |
---|---|

Title of host publication | 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 |

Publisher | Association for Computing Machinery, Inc |

Pages | 2567-2588 |

Number of pages | 22 |

ISBN (Electronic) | 9781611977554 |

DOIs | |

Publication status | Published - 2023 |

Event | 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 - Florence, Italy Duration: 22 Jan 2023 → 25 Jan 2023 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 2023-January |

### Conference

Conference | 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023 |
---|---|

Country/Territory | Italy |

City | Florence |

Period | 22/01/23 → 25/01/23 |

### Bibliographical note

Publisher Copyright:Copyright © 2023.