Round and Communication Efficient Graph Coloring
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.
Authors
- Gopinath Mishra (ORCID: https://orcid.org/0000-0003-0540-0292)
- Yi‐Jun Chang (ORCID: https://orcid.org/0000-0002-0109-2432)
- Hung Thuan Nguyen (ORCID: https://orcid.org/0009-0006-7993-2952)
- Farrel D Salim
Institutions
- National University of Singapore (SG)
Publication Details
- Published
- 2025-06-13
- DOI
- https://doi.org/10.1145/3732772.3733508
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Ministry of Education - Singapore