Georgia Institute of Technology College of Sciences

The chromatic polynomial $P_G(q)$ counts the number of proper $q$-colorings of a graph $G$. How many distinct chromatic polynomials arise from graphs on $n$ vertices? A conjecture of Bollobás, Pebody, and Riordan (2000) asserts that almost every graph is determined, up to isomorphism, by its chromatic polynomial. A weaker question is whether the number of distinct chromatic polynomials grows as $2^{\Theta(n^2)}$. We answer this question affirmatively. Our proof constructs a family of graphs whose chromatic polynomials encode a suitably chosen family of binary matrices. We recover these matrices through carefully chosen polynomial evaluations, together with a number-theoretic argument involving large prime factors of quadratic polynomials. The talk will also discuss related results on the number of distinct values attained by chromatic polynomials at fixed arguments. This is joint work with Cosmin Pohoata and Michael Zheng.