Recent breakthroughs in graph streaming have led to the design of single-pass semi-streaming algorithms for various graph coloring problems such as $(\Delta+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. We settle this fundamental question by proving that there is no deterministic single-pass semi-streaming algorithm that given a graph $G$ with maximum degree $\Delta$, can output a proper coloring of $G$ using any number of colors which is sub-exponential in $\Delta$. Our proof is based on analyzing the multi-party communication complexity of a related communication game, using random graph theory type arguments that may be of independent interest. We complement our lower bound by showing that just one extra pass over the input allows one to recover an $O(\Delta^2)$ coloring via a deterministic semi-streaming algorithm. This result is further extended to an $O(\Delta)$ coloring in $O(\log{\Delta})$ passes even in dynamic streams.

翻译：图表流中最近出现的突破导致设计了用于各种图表颜色问题的单流半流算法, 如$(\ Delta+1) $- 彩色、 色色变色、 三角无色图表等。 这些算法都是随机的, 关键的方式是随机的, 是否具有任何确定性类比, 在这项工作中仍然是一个重要的未决问题。 我们通过证明没有确定性的单流半流算法, 以最大度为$( Delta$) 的图形给出$G$, 能够使用以$( Delta$) 的分解颜色来输出适当的$G$。 我们的证据是基于分析相关通信游戏的多党通信复杂性, 使用随机图形理论类型参数, 可能具有独立的兴趣。 我们通过证明只有一次额外的输入允许一个人通过 $(\ Delta) $( $- 2) 的半流动算法, 将结果进一步扩展为 $( $D) 递增到 美元 流中 。