Low-Memory Algorithms for Online and W-Streaming Edge Coloring

Prantar Ghosh, Manuel Stoeckl

For edge coloring, the online and the W-streaming models seem somewhat orthogonal: the former needs edges to be assigned colors immediately after insertion, typically without any s…