Coloring Graphs with Few Colors in the Streaming Model

We study graph coloring problems in the streaming model, wherein the goal is to process an n-vertex graph whose edges arrive in a stream, using a limited space that is much smaller than the trivial O(n 2 ) bound. While prior work has largely focused on coloring graphs with a large number of colors-typically as a function of the maximum degree-we explore the opposite end of the spectrum: deciding whether the input graph can be colored using only a few, say, a constant number of colors. We are interested in each of the adversarial, random order, or dynamic streams, and-as is the standard in this model-focus solely on the space complexity rather than running time.

Our work lays the foundation for this new direction by establishing both upper and lower bounds on space complexity of key variants of the problem. Some of our main results include: * (