Charles Kenney, Rutgers University

Abstract

Let G be a graph on n vertices with maximum degree D. If we sample a list of (1+o(1)) ln(n) colors uniformly at random from {1,2,...,D+1}, independently for each vertex of G, then with high probability there is a proper coloring of G from these lists. This confirms a conjecture that Assadi expressed at this seminar in 2021. We overview the proof, discuss connections to other problems, and conclude with a couple conjectures of our own.

Joint work with Jeff Kahn.