µç³µÎÞÂë

Speaker:

Dan Dominik, Illinois Institute of Technology

Title:

Fractional DP-coloring of Graphs

Abstract:

Fractional coloring is linear programming relaxation of classic coloring of graphs where instead of assigning distinct colors, we assign disjoint sets of colors to adjacent vertices. Fractional coloring and its list coloring counterpart have been studied since the 1980s. A major result is that of Alon, Tuza, and Voigt (1997): the fractional chromatic number equals the fractional list chromatic number. DP-coloring (also called correspondence coloring) is a generalization of many notions of graph coloring, including classic coloring, list coloring and signed coloring, introduced by Dvořák and Postle in 2015. In 2019, Bernshteyn, Kostochka, and Zhu introduced a fractional version of DP-coloring. They showed that, unlike the fractional list chromatic number, the fractional DP-chromatic number of a graph can be arbitrarily larger than its fractional chromatic number.

In this talk, we generalize a result of Alon, Tuza, and Voigt (1997) on the fractional list chromatic number of odd cycles, and, in the process, show that the fractional DP-chromatic number for an odd cycle is equal to its fractional chromatic number. We show an upper bound for the fractional DP-chromatic number of multipartite graphs in terms of a recursive system of polynomial equations. Finally, we determine a lower bound on the fractional DP-chromatic number of \(K_{2,m}\). These last two results are based on probabilistic arguments.
This is joint work with Hemanshu Kaul and Jeffrey Mudrock.

 

Discrete Applied Math Seminar

Request Zoom Link