A celebrated result of Johansson in graph theory states that every triangle-free graph of maximum degree Δ can be properly colored with O(Δ/lnΔ) colors, improving upon the "greedy bound" of Δ+1 coloring in general graphs. This coloring can also be found in polynomial time. We present an algorithm for maintaining an O(Δ/lnΔ) coloring of a dynamically changing triangle-free graph that undergoes edge insertions and deletions. The algorithm is randomized and on n-vertex graphs has amortized update time of Δ^o(1) log(n) per update with high probability, even against an adaptive adversary. A key to the analysis of our algorithm is an application of the entropy compression method that to our knowledge is new in the context of dynamic algorithms. This technique appears general and is likely to find other applications in dynamic problems and thus can be of its own independent interest.

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.