2024/12/17 by Yi‐Jun Chang, Gopinath Mishra, Chang, Yi-Jun +5
Computer Science · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2412.12589
openalex publication_date 2024/12/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the context of communication complexity, we explore protocols for graph coloring, focusing on the vertex and edge coloring problems in n-vertex graphs G with a maximum degree Δ. We consider a scenario where the edges of G are partitioned between two players. Our first contribution is a randomized protocol that efficiently finds a (Δ+ 1)-vertex coloring of G, utilizing O(n) bits of communication in expectation and completing in O(log log n ⋅ log Δ) rounds in the worst case. This advancement represents a significant improvement over the work of Flin and Mittal [Distributed Computing 2025], who achieved the same communication cost but required O(n) rounds in expectation, thereby making a significant reduction in the round complexity. Our second contribution is a deterministic protocol to compute a (2Δ- 1)-edge coloring of G, which maintains the same O(n) bits of communication and uses only O(1) rounds. We complement the result with a tight Ω(n)-bit lower bound on the communication complexity of the (2Δ-1)-edge coloring problem, while a similar Ω(n) lower bound for the (Δ+1)-vertex coloring problem has been established by Flin and Mittal [Distributed Computing 2025]. Our result implies a space lower bound of Ω(n) bits for (2Δ- 1)-edge coloring in the W-streaming model, which is the first non-trivial space lower bound for edge coloring in the W-streaming model.