IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Counting colorings of triangle-free graphs

  • Oct. 22, 2021
  • 2:30 p.m.

Abstract

According to a celebrated theorem of Johansson, every triangle-free graph $G$ of maximum degree $\Delta$ has chromatic number $O(\Delta/\log\Delta)$. Molloy recently improved this upper bound to $(1+o(1))\Delta/\log\Delta$. In this talk, we will strengthen Molloy’s result by establishing an optimal lower bound on the number of proper $q$-colorings of $G$ when $q$ is at least $(1+o(1))\Delta/\log\Delta$. One of the main ingredients in our argument is a novel proof technique introduced by Rosenfeld. This is joint work with Tyler Brazelton, Ruijia Cao, and Akum Kang.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC