Deterministic graph coloring in the streaming model
Sepehr Assadi, Andrew Tzer-Yeu Chen, Glenn Sun · 2022
Recent breakthroughs in graph streaming have led to design of semi-streaming algorithms for various graph coloring problems such as (Δ+1)-coloring, degeneracy-coloring, coloring triangle-free graphs, and others. These algorithms are all randomized in crucial ways and whether or not there is any deterministic analogue of them has remained an important open question in this line of work.