Cover Image

Online Edge Coloring: Sharp Thresholds

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Blikstad, Joakim, Svensson, Ola, Vintan, Radu, Wajc, David
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Deterministic Online Bipartite Edge Coloring
by: Blikstad, Joakim, et al.
Published: (2024)

Online Edge Coloring is (Nearly) as Easy as Offline
by: Blikstad, Joakim, et al.
Published: (2024)

Deterministic Edge Coloring with few Colors in CONGEST
by: Blikstad, Joakim, et al.
Published: (2026)

Efficient Matroid Intersection via a Batch-Update Auction Algorithm
by: Blikstad, Joakim, et al.
Published: (2024)

Global vs. s-t Vertex Connectivity Beyond Sequential: Almost-Perfect Reductions & Near-Optimal Separations
by: Blikstad, Joakim, et al.
Published: (2025)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
by: Joseph, et al.
Published: (2023)

Online Matching: A Brief Survey
by: Huang, Zhiyi, et al.
Published: (2024)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
by: Bernstein, Aaron, et al.
Published: (2024)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
by: Bernstein, Aaron, et al.
Published: (2025)

New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling
by: Braverman, Mark, et al.
Published: (2024)

Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes
by: Buchbinder, Niv, et al.
Published: (2025)

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
by: Bhattacharya, Sayan, et al.
Published: (2023)

Greedy Algorithms for Shortcut Sets and Hopsets
by: Bals, Ben, et al.
Published: (2025)

A Strong Linear Programming Relaxation for Weighted Tree Augmentation
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Dynamic Edge Coloring of Forests
by: Kaplan, Haim, et al.
Published: (2026)

Combinatorial Stationary Prophet Inequalities
by: Patel, Neel, et al.
Published: (2023)

Coloring 3-Colorable Graphs with Low Threshold Rank
by: Hsieh, Jun-Ting
Published: (2025)

Dimension-Free Correlated Sampling for the Hypersimplex
by: Joseph, et al.
Published: (2025)

The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
by: Ma, Will, et al.
Published: (2019)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Data-Driven Solution Portfolios
by: Drygala, Marina, et al.
Published: (2024)

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

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
by: Lee, Euiwoong, et al.
Published: (2024)

Faster Edge Coloring by Partition Sieving
by: Akmal, Shyan, et al.
Published: (2025)

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

On the Complexity of Distributed Edge Coloring and Orientation Problems
by: Brandt, Sebastian, et al.
Published: (2025)

Overlapping and Robust Edge-Colored Clustering in Hypergraphs
by: Crane, Alex, et al.
Published: (2023)

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

Retriever Portfolios: A Principled Approach to Adaptive RAG
by: Stouras, Miltiadis, et al.
Published: (2026)

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

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

Online Coloring for Graphs of Large Odd Girth
by: Yoneda, Hirotaka, et al.
Published: (2026)

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

On $b$-Matching and Fully-Dynamic Maximum $k$-Edge Coloring
by: El-Hayek, Antoine, et al.
Published: (2023)

On the FirstFit Algorithm for Online Unit-Interval Coloring
by: Krekelberg, Bob, et al.
Published: (2025)

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

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
by: Jiang, Tianle, et al.
Published: (2024)

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

Faster MAX-CUT on Bounded Threshold Rank Graphs
by: Anderson, Prashanti, et al.
Published: (2025)