EE ZOOM Seminar: Density-Sensitive Algorithms for (∆ + 1)-Edge Coloring
https://tau-ac-il.zoom.us/j/89578018616
Electrical Engineering Systems ZOOM Seminar
Speaker: Nadav Panski
M.Sc. student under the supervision of Prof. Shay Solomon
Monday, 4th August 2025, at 15:00
Density-Sensitive Algorithms for (∆ + 1)-Edge Coloring
Abstract
An edge coloring of a graph G is a function that assigns one color from a given set of colors to each edge of G such that no two adjacent edges share the same color. Clearly, at least ∆ colors are required, where ∆ = ∆(G) denotes the maximum degree of G. Vizing’s theorem states that any graph can be colored with at most ∆ + 1 colors. Since the problem of determining if a graph can be colored with exactly ∆ colors is NP-hard, a natural goal is to optimize the running time of (∆ + 1)-edge coloring algorithms.
Several polynomial time (∆ + 1)-edge coloring algorithms was known, and the state-of-the-art running time (up to polylogarithmic factors) was O(min{mn, m∆})
by Gabow, Nishizeki, Kariv, Leven and Terada from 1985, where n and m denote the number of vertices and edges in the graph, respectively. Recently, Sinnamon shavedoff a polylog(n) factor from the time bound of Gabow et al.
The arboricity α = α(G) of a graph G is the minimum number of edge-disjoint forests into which its edge set can be partitioned, and it is a measure of the graph’s “uniform density”. While α ≤ ∆ in any graph, many natural and real-world graphsexhibit a significant separation between α and ∆.
In our work we design a (∆ + 1)-edge coloring algorithm with a running time of Ominmn, m∆α∆
, thus improving the longstanding time barrier by a factor of α∆
. In particular, we achieve a near-linear runtime for bounded arboricity graphs (i.e., α=O(1)
) as well as when α = α=O(∆n)
. Our algorithm builds on Gabow et al.’s and Sinnamon’s algorithms, and can be viewed as a density-sensitive refinement of them.
This presentation will present the edge-coloring problem, explore known methods and algorithms for (∆ + 1)-edge coloring, and introduce our new techniques for dealing with this problem and our results.
השתתפות בסמינר תיתן קרדיט שמיעה = עפ"י רישום בצ'ט של שם מלא + מספר ת.ז.
