On Proportional 2-Choosability of Graphs with a Bounded Palette

Speaker: 

Paul Shin, College of Lake County

Description: 

This talk will be on a variation of the classical vertex coloring problem in graph theory.  In this problem, we seek to assign a color to each vertex of a graph so that no two adjacent vertices receive the same color (a so-called proper coloring).  List coloring is a well-known variation where each vertex of a graph receives a list of available colors, and we seek to find a proper coloring of the graph such that each vertex receives a color from its corresponding list. Many applications of classical vertex coloring and list coloring have appeared in the literature. In some applications, such as when colors represent resources that need to be distributed in a network, we wish to find a proper coloring that does not overuse or underuse any color.  In 2019 Kaul, Mudrock, Pelsmajer and Reiniger introduced a version of list coloring called proportional choosability that adds this additional requirement.  In this talk we study proportional choosability when: all lists must be of size two and the colors that may appear in each list is restricted.

This is joint work with Jeffrey Mudrock, Robert Piechota, and Tim Wagstrom.

Event Topic

Discrete Applied Math Seminar