3 papers
cs.DS2026
Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
Sepehr Assadi, Helia Yazdanyar
A celebrated result of Johansson in graph theory states that every triangle-free graph of maximum degree can be properly colored with colors, improving upon the…
cs.DS2026
Simple Sublinear Algorithms for Vertex Coloring via Asymmetric Palette Sparsification
Sepehr Assadi, Helia Yazdanyar
The palette sparsification theorem (PST) of Assadi, Chen, and Khanna (SODA 2019) states that in every graph with maximum degree , sampling a list of colors fro…
cs.DS2025
Coloring Graphs with Few Colors in the Streaming Model
Sepehr Assadi, Janani Sundaresan, Helia Yazdanyar
We study graph coloring problems in the streaming model, where the goal is to process an -vertex graph whose edges arrive in a stream, using a limited space that is smaller than…