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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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