Distributed minimum vertex coloring and maximum independent set in chordal graphs

We give deterministic distributed (1+ϵ)-approximation algorithms for Minimum Vertex Coloring and Maximum Independent Set on chordal graphs in the LOCAL model. Our coloring algorithm runs in O(1ϵlog⁡n) rounds, and our independent set algorithm has a runtime of O(1ϵlog⁡(1ϵ)log⁎⁡n) rounds. For coloring, existing lower bounds imply that the dependencies on 1ϵ and log⁡n are best possible. For independent set, we prove that Ω(1ϵ) rounds are necessary.