Sampling from the proper colorings of a graph using a number of colors linear in the maximum degree in expected linear time (Mark Huber, CMC)

Abstract: A proper coloring of a graph is an assignment of colors from \( \{1, 2, \ldots, k\} \) to each node of a graph such that no two nodes connected by an edge receive the same color. Let \( \Delta \) denote the maximum degree of the graph. If \( k \geq \Delta + 1 \) then at least one proper coloring always exists. However, counting the number of proper colorings of an arbitrary graph is a #P-complete problem, even when \( \Delta = 3 \). This means finding a polynomial time exact algorithm is unlikely to be found. On the other hand, if a user can sample uniformly at random from the proper colorings of a graph, then it becomes possible to approximately count the number of proper colorings to arbitrary precision in polynomial time. This work presents the first algorithm that has an expected running time that is linear in the size of the graph under the condition that \( k > 3.637 \Delta \). Joint work with Kritika Bhandari.