Cover Image

Beyond Brooks: $(Δ-1)$-Coloring in Semi-Streaming

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Flin, Maxime, Halldórsson, Magnús M.
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Faster Dynamic $(Δ+1)$-Coloring Against Adaptive Adversaries
by: Flin, Maxime, et al.
Published: (2025)

Decentralized Distributed Graph Coloring II: degree+1-Coloring Virtual Graphs
by: Flin, Maxime, et al.
Published: (2024)

$(Δ+ 1)$ Vertex Coloring in $O(n)$ Communication
by: Flin, Maxime, et al.
Published: (2024)

Sublogarithmic Distributed Vertex Coloring with Optimal Number of Colors
by: Flin, Maxime, et al.
Published: (2026)

Decentralized Distributed Graph Coloring: Cluster Graphs
by: Flin, Maxime, et al.
Published: (2024)

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

When MIS and Maximal Matching are Easy in the Congested Clique
by: Censor-Hillel, Keren, et al.
Published: (2025)

Streaming Diameter of High-Dimensional Points
by: Halldórsson, Magnús M., et al.
Published: (2025)

Distributed Delta-Coloring under Bandwidth Limitations
by: Maus, Yannic, et al.
Published: (2024)

Unit Interval Selection in Random Order Streams
by: Alexandru, Cezar-Mihail, et al.
Published: (2026)

Dynamic $(Δ+ 1)$ Vertex Coloring
by: Benson-Tilsen, Noam
Published: (2026)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
by: Behnezhad, Soheil, et al.
Published: (2024)

Sampling Proper Colorings on Line Graphs Using $(1+o(1))Δ$ Colors
by: Wang, Yulin, et al.
Published: (2023)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2024)

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

Distributed Lovász Local Lemma under Bandwidth Limitations
by: Halldórsson, Magnús M., et al.
Published: (2024)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
by: Fischer, Manuela, et al.
Published: (2021)

Semi-Streaming Algorithms for Hypergraph Matching
by: Reinstädtler, Henrik, et al.
Published: (2025)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
by: Elkin, Michael, et al.
Published: (2024)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
by: Bhattacharya, Sayan, et al.
Published: (2024)

Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs
by: Dhawan, Abhishek
Published: (2024)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
by: Ferdous, S M, et al.
Published: (2023)

Improved Streaming Edge Coloring
by: Chechik, Shiri, et al.
Published: (2025)

Faster Deterministic Streaming Vertex Coloring
by: Chechik, Shiri, et al.
Published: (2026)

Streaming Edge Coloring with Subquadratic Palette Size
by: Chechik, Shiri, et al.
Published: (2023)

Semi-Streaming Algorithms for Submodular Maximization under Random Arrival Order
by: Buchbinder, Niv, et al.
Published: (2026)

Perfect Sampling in Turnstile Streams Beyond Small Moments
by: Woodruff, David P., et al.
Published: (2025)

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
by: Alipour, Sharareh, et al.
Published: (2025)

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

Engineering Fully Dynamic Exact $Δ$-Orientation Algorithms
by: Großmann, Ernestine, et al.
Published: (2024)

Edge-coloring sparse graphs with $Δ$ colors in quasilinear time
by: Kowalik, Lukasz
Published: (2024)

$Δ$-Motif: Parallel Subgraph Isomorphism via Tabular Operations
by: Wang, Yulun, et al.
Published: (2025)

Coloring Graphs with Few Colors in the Streaming Model
by: Assadi, Sepehr, et al.
Published: (2025)

Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring
by: Sadeh, Yaniv, et al.
Published: (2026)

Unbiased Insights: Optimal Streaming Algorithms for $\ell_p$ Sampling, the Forget Model, and Beyond
by: Lin, Honghao, et al.
Published: (2025)

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

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

Comparing the Hardness of Online Minimization and Maximization Problems with Predictions
by: Berg, Magnus
Published: (2024)

Faster Distributed $Δ$-Coloring via Ruling Subgraphs
by: Bourreau, Yann, et al.
Published: (2025)