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 \geq \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