Streaming Edge Coloring with Subquadratic Palette Size

Shiri Chechik, Doron Mukhtar, Tianyi Zhang

In this paper, we study the problem of computing an edge-coloring in the (one-pass) W-streaming model. In this setting, the edges of an $n$-node graph arrive in an arbitrary order…