Cover Image

Coloring Graphs with Few Colors in the Streaming Model

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Assadi, Sepehr, Sundaresan, Janani, Yazdanyar, Helia
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
by: Assadi, Sepehr, et al.
Published: (2026)

Distributed Triangle Detection is Hard in Few Rounds
by: Assadi, Sepehr, et al.
Published: (2025)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
by: Assadi, Sepehr, et al.
Published: (2025)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
by: Assadi, Sepehr
Published: (2024)

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring
by: Assadi, Sepehr, et al.
Published: (2022)

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming
by: Das, Avinandan
Published: (2026)

Neighborhood-Aware Graph Labeling Problem
by: Shahverdikondori, Mohammad, et al.
Published: (2026)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
by: Moka, Sarat, et al.
Published: (2026)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
by: Baril, Ambroise, et al.
Published: (2025)

On the Parameterized Complexity of Odd Coloring
by: Bhyravarapu, Sriram, et al.
Published: (2025)

Kernelization Bounds for Constrained Coloring
by: Haviv, Ishay
Published: (2026)

Semi-Streaming Algorithms for Graph Property Certification
by: Das, Avinandan, et al.
Published: (2025)

A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
by: Assadi, Sepehr
Published: (2023)

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
by: Abboud, Amir, et al.
Published: (2026)

Deterministic Independent Sets in the Semi-Streaming Model
by: Ye, Daniel
Published: (2025)

A Fast Coloring Oracle for Average Case Hypergraphs
by: Marcussen, Cassandra, et al.
Published: (2025)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
by: Jiang, Cheng, et al.
Published: (2026)

Streaming Zero-Knowledge Proofs
by: Cormode, Graham, et al.
Published: (2023)

Streaming approximation resistance of every ordering CSP
by: Singer, Noah G., et al.
Published: (2021)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
by: Fei, Yumou, et al.
Published: (2025)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
by: Li, Qian, et al.
Published: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Characterizing Streaming Decidability of CSPs via Non-Redundancy
by: Sharma, Amatya, et al.
Published: (2026)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
by: Jonsson, Peter, et al.
Published: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
by: Aute, Shubhada, et al.
Published: (2026)

An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication
by: Assadi, Sepehr, et al.
Published: (2025)

A New Information Complexity Measure for Multi-pass Streaming with Applications
by: Braverman, Mark, et al.
Published: (2024)

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
by: Kocurek, Nicholas, et al.
Published: (2026)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
by: Moroie, Gregory
Published: (2025)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

Efficient Catalytic Graph Algorithms
by: Cook, James, et al.
Published: (2025)