Showing cs.DCShow all
3 papers · 1 filter
cs.DC2025
Decentralized Distributed Graph Coloring: Cluster Graphs
Maxime Flin, Magnus M. Halldorsson, Alexandre Nolin
Graph coloring is fundamental to distributed computing. We give the first sub-logarithmic distributed algorithm for coloring cluster graphs. These graphs are obtained from the unde…
cs.DC2025
Faster Distributed -Coloring via Ruling Subgraphs
Yann Bourreau, Sebastian Brandt, Alexandre Nolin
Brooks' theorem states that all connected graphs but odd cycles and cliques can be colored with colors, where is the maximum degree of the graph. Such colorings have been…
cs.DC2024
Decentralized Distributed Graph Coloring II: degree+1-Coloring Virtual Graphs
Maxime Flin, Magnús M. Halldórsson, Alexandre Nolin
Graph coloring is fundamental to distributed computing. We give the first general treatment of the coloring of virtual graphs, where the graph to be colored is locally embedded…