Proportional Choosability: A New List Analogue of Equitable Coloring

The study of equitable coloring began with a conjecture of Erdos in 1964, and it was formally introduced by Meyer in 1973. An equitable \(k\)-coloring of a graph \(G\) is a proper \(k\)-coloring of \(G\) such that the sizes of the color classes differ by at most one. In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring, called equitable choosability. Specifically, given lists of available colors of size \(k\) at each vertex of a graph \(G\), a proper list coloring is equitable if each color appears on at most \(\lceil |V(G)|/k\rceil\) vertices. Graph \(G\) is equitably \(k\)-choosable if such a coloring exists whenever all the lists have size \(k\).

In this talk we introduce a new list analogue of equitable coloring which we call proportional choosability. For this new notion, the number of times we use a color must be proportional to the number of lists in which the color appears. Proportional \(k\)-choosability implies both equitable \(k\)-choosability and equitable \(k\)-colorability, and the graph property of being proportionally \(k\)-choosable is monotone. We will discuss proportional choosability of graphs with small order, completely characterize proportionally \(2\)-choosable graphs, and illustrate some of the techniques we have used to prove results. This is joint work with Hemanshu Kaul, Michael Pelsmajer, and Benjamin Reiniger.

Event Topic

Discrete Applied Math Seminar