Sepehr Assadi, Princeton University

Abstract

We prove that for every graph with maximum degree Delta, if we sample O(log n) colors independently and uniformly at random for each vertex from colors {1,...,Delta+1}, then with high probability, there is a proper coloring of G using only the sampled colors for each vertex. We discuss the origins of this problem in sublinear algorithms for graph coloring, some of its connection to classical work in graph theory, and its more recent extensions to other graph coloring problems.

Based on the following joint work:

https://arxiv.org/abs/1807.08886 with Yu Chen and Sanjeev Khanna;
https://arxiv.org/abs/2006.10456 with Noga Alon;
https://arxiv.org/abs/2109.14891 with Andrew Chen and Glenn Sun.

See: https://sites.google.com/view/rutgersdmseminar