2 papers
cs.DC2025
Faster Distributed -Coloring via a Reduction to MIS
Yann Bourreau, Sebastian Brandt, Alexandre Nolin
Recent improvements on the deterministic complexities of fundamental graph problems in the LOCAL model of distributed computing have yielded state-of-the-art upper bounds of $\tild…
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…