Discrete Applied Math Seminar by Jeffrey Mudrock: Counting Packings of List Colorings of Graphs

Speaker: Jeffrey Mudrock, University of South Alabama

Title: Counting Packings of List Colorings of Graphs

Abstract:

List packing is a relatively new notion that was first suggested by Alon, Fellows, and Hare in 1996, but the suggestion was not formally embraced until a recent paper of Cambie, Cames van Batenburg, Davies, and Kang in 2021. Given a list assignment for a graph, list packing asks for the existence of multiple pairwise disjoint list colorings of the graph. Several papers have recently appeared that study the existence of such a packing of list colorings. In this talk we consider counting these packings. 

We define the list packing function of a graph G as the guaranteed number of proper L-packings of a prescribed size over all list assignments L that assign the same number of colors to each vertex of G. In the case the prescribed size is one, the list packing function of G is equal to its list color function (the list color function of G is the well-studied list analogue of the chromatic polynomial of G). Inspired by the well-known behavior of list color functions and chromatic polynomials, we consider the list packing function of a graph in comparison to its classical coloring counterpart. This leads to a generalization of a recent theorem of Dong and Zhang (2023), which improved results going back to Donner (1992), about when the list color function of a graph equals its chromatic polynomial. Further, we show how a polynomial method can be used to generalize bounds on the list packing number of sparse graphs to exponential lower bounds on the corresponding list packing functions.

This is joint work with Hemanshu Kaul.

 

Discrete Applied Math Seminar

Request Zoom Link