We explore the question how well we can color graphs in distributed models, especially in graph classes for which Δ + 1-colorings provide no approximation guarantees. We particularly focus on interval graphs.
model, we give an algorithm that computes a constant factor approximation to the coloring problem on interval graphs in O(log
) rounds, which is best possible. The result holds also for the
model when the representation of the nodes as intervals is given.
We then consider restricted beep models, where communication is restricted to the aggregate acknowledgment of whether a node’s attempted coloring succeeds. We apply an algorithm designed for the SINR model and give a simplified proof of a
)-approximation. We show a nearly matching Ω(log
)-approximation lower bound in that model.