Discrete Applied Mathematics Seminar by Sarah Allred: Enumerative Chromatic-Choosability

Speaker: Sarah Allred, assistant professor of mathematics, University of South Alabama

Title: Enumerative Chromatic-Choosability

Abstract: Counting proper (classical) colorings of graphs is a fundamental topic in enumerative combinatorics that has been extensively studied since the early 20th century. The chromatic polynomial of a graph $G$, denoted $P(G,m)$, is equal to the number of proper $m$-colorings of $G$. List coloring is a well-studied generalization of classical coloring that was introduced in the 1970s. A graph $G$ is chromatic-choosable when its list chromatic number ${\chi }_{\ell }(G)$ is equal to its chromatic number $chi(G)$. Chromatic-choosability is a well-studied topic, and in fact, some of the most famous results and conjectures related to list coloring involve chromatic-choosability.
In 1990, Kostochka and Sidorenko introduced the list color function of a graph $G$, denoted $P_{\ell }(G,m)$. The list color function of $G$ is the list analogue of $P(G,m)$. A graph is said to be enumeratively chromatic-choosable if $P(G,m)=P_{\ell }(G,m)$ whenever $m\ge \chi (G)$. In this talk, I will present some results and open questions on enumerative chromatic-choosability. In particular, I give a characterization of enumeratively 2-chromatic-choosable graphs and explore the effect that joining a complete graph to an arbitrary graph has on enumerative chromatic-choosability.
This is joint work with Jeff Mudrock.

 

Discrete Applied Math Seminar

Request Zoom Link