Edge Coloring

One computational problem that I am particularly interested in is edge coloring. Given a graph $G = (V, E)$, the edge coloring problem asks us to find a mapping (referred to as a coloring) $\chi : E \longrightarrow C$ from $E$ to some set of colors $C$ such that any two edges $e, f \in E$ sharing an endpoint receive different colors. If the maximum degree of $G$ is $\Delta$, it is easy to see that at least $\Delta$ colors are required for such a coloring to exist. Remarkably, Vizing showed that it is always possible to find such a coloring that uses at most $\Delta + 1$ many colors. In many computational models, it is fairly trivial to obtain a $2 \Delta - 1$-coloring. Combining this with the fact that it's NP-Hard to determine whether a graph admits a $\Delta$-coloring, we get very tight upper and lower bounds on what we can hope to achieve across these various computational models, leading to a very rich landscape where in each setting the goal is to increase the quality of our coloring from $2 \Delta - 1$ to $\Delta + 1$ while sacrificing as little as possible along the way.

Dynamic Edge Coloring Simulation

This is an implementation of a dynamic edge coloring algorithm that explicitly maintains the output of the online algorithm of Bar-Noy et al. [BMN92] on a random permutation of the edges of a dynamic graph as it undergoes edge insertions and deletions. The dynamization follows from the ideas and data structures presented in [BCPS23]. The underlying dynamic graph in this implementation is defined by a simple physics simulation of points (corresponding to nodes) interacting in a force field, where (roughly speaking) edges are inserted/deleted between pairs of nodes when they get sufficiently close/far apart.

The code for this implementation is contained in this repository.

Papers

The following are some links to papers on edge coloring in the static, dynamic, distributed, online, and streaming settings. While these results may seem to be very different, many of them rely on a few fundamental ideas and techniques that can be seen recurring in the literature, spanning back many decades.

[ABBCSZ24] S. Assadi, S. Behnezhad, S. Bhattacharya, M. Costa, S. Solomon, and T. Zhang. Vizing's Theorem in Near-Linear Time.

• • $(\Delta + 1)$-coloring in $O(m \log \Delta)$ time (static)

[BCSZ24] S. Bhattacharya, M. Costa, S. Solomon, and T. Zhang. Even Faster $(\Delta + 1)$-Edge Coloring via Multi-Step Vizing Chains.

• • $(\Delta + 1)$-coloring in $\tilde O(mn^{1/4})$ time (static)

[BD24] A. Bernshteyn and A. Dhawan. A Linear-Time Algorithm for $(1 + \epsilon)\Delta$-Edge-Coloring.

• • $(1 + \epsilon)\Delta$-coloring in $O(m \poly(1/\epsilon))$ time for any $\epsilon \geq 1/\Delta$ (static)

[DGS24] A. Dudeja, R. Goswami, and M. Saks. Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs.

• • Greedy $(1 + \epsilon)\Delta$-coloring in the online setting for dense graphs (online)

  • Greedy $(1 + \epsilon)\Delta$-coloring in the random-order online setting (online - random order)

  • Deterministic $(1 + \epsilon)\Delta$-coloring in the online setting for dense graphs (online - deterministic)

[BCCSZ24] S. Bhattacharya, D. Carmon, M. Costa, S. Solomon, and T. Zhang. Faster $(\Delta + 1)$-Edge Coloring: Breaking the $m \sqrt n$ Time Barrier.

• • $(\Delta + 1)$-coloring in $\tilde O(mn^{1/3})$ time (static)

[Ass24] S. Assadi. Faster Vizing and Near-Vizing Edge Coloring Algorithms.

• • $(\Delta + O(\log n))$-coloring in $\tilde O(m)$ time (static)

  • $(\Delta + 1)$-coloring in $\tilde O(n^2)$ time (static)

[BSVW24] J. Blikstad, O. Svensson, R. Vintan, and D. Wajc. Online Edge Coloring is (Nearly) as Easy as Offline.

• • $(1 + o(1))\Delta$-coloring in the online setting (online)

[Chr24] A. Christiansen. Deterministic Dynamic Edge-Colouring.

• • Deterministic $(1 + \epsilon)\Delta$-coloring in $n^{o(1)}$ update time (fully dynamic - deterministic, amortized)

[Kow24] Łukasz Kowalik. Edge-coloring sparse graphs with $\Delta$ colors in quasilinear time.

• • $\Delta$-coloring in $\tilde O(m)$ time for graphs of bounded maximum average degree (static)

[EK24] M. Elkin and A. Khuzman. Deterministic Simple $(1 + \epsilon)\Delta$-Edge-Coloring in Near-Linear Time.

• • Deterministic $(1 + \epsilon)\Delta$-coloring in $\tilde O(m)$ time (static)

[BCPS23] S. Bhattacharya, M. Costa, N. Panski, and S. Solomon. Arboricity-Dependent Algorithms for Edge Coloring.

• • $(\Delta + O(\alpha))$-coloring in $\tilde O(m)$ time (static)

  • $(\Delta + O(\alpha))$-coloring in $\polylog(n)$ update time (fully dynamic - deterministic, amortized)

[BSVW23] J. Blikstad, O. Svensson, R. Vintan, and D. Wajc. Simple and Asymptotically Optimal Online Bipartite Edge Coloring.

• • $(1 + o(1))\Delta$-coloring in bipartite graphs under one-sided vertex arrivals (online)

[BCPS23] S. Bhattacharya, M. Costa, N. Panski, and S. Solomon. Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time.

• • $(1 + \epsilon)\Delta$-coloring in $\poly(1/\epsilon)$ update time (fully dynamic - oblivious adversary, worst case)

  • $(1 + \epsilon)\Delta$-coloring in $O(m \poly(1/\epsilon))$ time (static)

  • Analysis of the 'gentle' nibble method by subsampling to locally treelike graphs (static)

[BCPS23] S. Bhattacharya, M. Costa, N. Panski, and S. Solomon. Density-Sensitive Algorithms for $(\Delta + 1)$-Edge Coloring.

• • $(\Delta + 1)$-coloring in $\tilde O(m \alpha)$ time (static)

[BS23] S. Behnezhad and M. Saneian. Streaming Edge Coloring with Asymptotically Optimal Colors.

• • $O(\Delta^{1.5}/s + \Delta)$-edge coloring with $\tilde O(ns)$ space (streaming)

[Chr22] A. Christiansen. The Power of Multi-Step Vizing Chains.

• Augmenting subgraph of size $O(\Delta^7 \log n)$ for any uncolored edge (structural)

• $(1 + \epsilon)\Delta$-coloring in $\tilde O(1)$ update time (fully dynamic - adaptive adversary, worst case)

• Deterministic LOCAL algorithm for $\Delta + 1$-coloring in $\tilde O(\poly(\Delta) \log^6 n)$ rounds (distributed - LOCAL, deterministic)

[KLSST21] J. Kulkarni, Y. Liu, A. Sah, M. Sawhney, and J. Tarnawski. Online Edge Coloring via Tree Recurrences and Correlation Decay.

• • $(e/(e-1) + o(1))\Delta$-coloring in the online setting (online - oblivious adversary)

[SW21] A. Saberi and D. Wajc. The Greedy Algorithm is \emph{not} Optimal for On-Line Edge Coloring.

• • $(1.9 + o(1))\Delta$-coloring in the online setting under vertex arrivals (online - oblivious adversary)

[BGW21] S. Bhattacharya, F. Grandoni, and D. Wajc. Online Edge Coloring Algorithms via the Nibble Method.

• • $(1 + o(1))\Delta$-coloring in the random-order online setting (online - random order)

  • $(1 + \epsilon)\Delta$-coloring with $\poly(1/\epsilon)$ recourse (fully dynamic - oblivious adversary, worst case)

  • Analysis of the 'gentle' nibble method (static)

[CPW19] I. Cohen, B. Peng, and D. Wajc. Tight Bounds for Online Edge Coloring.

• • $(1 + o(1))\Delta$-coloring in bipartite graphs under one-sided vertex arrivals (online)

[DHZ19] R. Duan, H. He, and T. Zhang. Dynamic Edge Coloring with Improved Approximation.

• • $(1 + \epsilon)\Delta$-coloring in $\tilde O(1)$ update time (fully dynamic - adaptive adversary, amortized)

[Sin19] C. Sinnamon. Fast and Simple Edge-Coloring Algorithms.

• • $(\Delta + 1)$-coloring in $O(m \sqrt n)$ time (static)

[CHLPU18] Y. Chang, Q. He, W. Li, S. Pettie, and J. Uitto. The Complexity of Distributed Edge Coloring with Small Palettes.

• • Randomized LOCAL algorithm for $\Delta + \tilde O(\sqrt \Delta)$-coloring in $\tilde O(1)$ rounds (distributed - LOCAL, randomized)

  • $\Omega((\Delta/c) \log (cn/\Delta))$ recourse lower bounds for extending partial $(\Delta + c)$-colorings (structural)

[BCHN17] S. Bhattacharya, D. Chakrabarty, M. Henzinger, and D. Nanongkai. Dynamic Algorithms for Graph Coloring.

• • Deterministic $2\Delta-1$-coloring in $O(\log \Delta)$ update time (fully dynamic - adaptive adversary, worst case)

[BM17] L. Barenboim and T. Maimon. Fully-Dynamic Graph Algorithms with Sublinear Time Inspired by Distributed Computing.

• • $O(\Delta)$-coloring in $\tilde O(\sqrt \Delta)$ update time (fully dynamic - deterministic, worst case)

[MR00] M. Molloy and B. Reed. Near-Optimal List Colorings.

• • Analysis of the 'aggressive' nibble method using Talagrand's isoperimetric inequality (static)

[DGP96] D. Dubhashi, D. Grable, and A. Panconesi. Near-Optimal, Distributed Edge Colouring via the Nibble Method.

• • Analysis of the 'gentle' nibble method (static)

[BMN92] A. Bar-Noy, R. Motwani, J. Naor. The greedy algorithm is optimal for on-line edge coloring.

• • Lower bounds for online edge coloring when $\Delta = O(\log n)$ (online)

[KS85] H. Karloff and D. Shmoys. Efficient Parallel Algorithms for Edge Coloring Problems.

• • $(\Delta + O(\Delta^{0.5 + \epsilon}))$-coloring in $\tilde O(m)$ time (static)

[GNKLT85] H. Gabow, T. Nishizeki, O. Kariv, D. Leven, and O. Terada. Algorithms for Edge-Coloring Graphs.

• • $(\Delta + 1)$-coloring in $O(m \sqrt{n \log n})$ time (static)

[Hol81] I. Holyer. The NP-Completeness of Edge-Coloring.

• • NP-Completeness of determining the chromatic index of a graph (static)

[Viz64] V. Vizing. On an estimate of the chromatic class of a p-graph.

• • $\Delta + 1$-coloring in $O(mn)$ time (static)