Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring
Every graph with maximum degree $\Delta$ can be colored with $(\Delta+1)$ colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model. But, in reality, one almost never needs $(\Delta+1)$ colors to properly color a grap...
| Asıl Yazarlar: | , , |
|---|---|
| Materyal Türü: | Makale |
| Dil: | English |
| Baskı/Yayın Bilgisi: |
TheoretiCS Foundation e.V.
2023-08-01
|
| Seri Bilgileri: | TheoretiCS |
| Konular: | |
| Online Erişim: | https://theoretics.episciences.org/9739/pdf |