Discrete Applied Math Seminar by Gunjan Sharma: Extremal and Enumerative Problems on DP-Coloring of Graphs

Speaker: Gunjan Sharma, Illinois Institute of Technology

Title: Extremal and Enumerative Problems on DP-Coloring of Graphs

Abstract: DP-coloring (also called correspondence coloring) introduced by Dvorak and Postle in 2015 is a generalization of list coloring, a widely studied topic in Chromatic Graph Theory. Intuitively, DP-coloring considers the worst-case scenario of how many colors we have to use in a list coloring if we no longer can identify the names of the colors.

We study DP-coloring of Cartesian product of graphs and give a straightforward upper bound on the DP-chromatic number of the Cartesian product of two graphs in terms of the DP-chromatic numbers and the coloring numbers of the factors, by generalizing the corresponding list coloring arguments. Our main focus is the study of the problems arising out of showing the sharpness for this bound. We introduce new tools to study lower bounds on the DP-chromatic number, and we illustrate the importance of the DP color function (the function that enumerates DP-colorings as a DP-coloring counterpart of the chromatic polynomial) in building these lower bounds using partially-random constructions.

Additionally we make partial progress on open problems on DP-coloring tensor product of graphs, Shameful conjecture analogues for list coloring and DP-coloring and the log-concavity of the list color function and the DP color function.

 

Discrete Applied Mathematics Seminar