Distance-2 Coloring in the CONGEST Model

DOI10.1145/3382734.3405706MaRDI QIDQ5855241zbMATH OpenOpenAlexFDO

Authors Magnús M. Halldórsson, Fabian Kuhn, Yannic Maus

Publication date 15 March 2021

Published in Proceedings of the 39th Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.06528

zbMATH Keywords

distance-2 coloringpower graphCONGEST modeldistributed graph coloring

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Recommendations

• Wegner's conjecture on 2-distance coloring
• Distance-two coloring of sparse graphs
• The distance coloring of graphs
• Further results on 2-distance coloring of graphs
• 2-distance colorings of integer distance graphs
• 2-distance coloring of sparse graphs
• 2-distance coloring of sparse graphs
• Colorings of distance graphs
• On distance graph coloring problems
• \((\Delta+1)\) coloring in the congested clique model

Cited in

(6)

• Sampling and output estimation in distributed algorithms and LCAs
• Distributed Testing of Distance-k Colorings
• Distributed Symmetry Breaking on Power Graphs via Sparsification
• -binding functions for squares of convex bipartite graphs and partite testability for bipartite squares
• Distributed symmetry breaking on power graphs via sparsification
• Coloring fast without learning your neighbors' colors

This page was built for publication: Distance-2 Coloring in the CONGEST Model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5855241)