Discrete Applied Mathematics Seminar by Dan Dominik: Fractional Degeneracy of Graphs
Speaker: , mathematics faculty, Thornton Township High School
Title: Fractional Degeneracy of Graphs
Abstract:
Fractional versions of graph coloring problems have a long history. DP-coloring was introduced as a generalization of ordinary and list colorings of graphs by Dvo\v{r}\'{a}k and Postle in 2015. In this talk we will discuss the fractional version of DP-coloring which was first studied by Bernshteyn, Kostochka, and Zhu in 2019.
The degeneracy of a graph is a commonly used "greedy bound" on many variants of the chromatic number of a graph. Over the past few years, many authors have introduced variations of degeneracy and used them to provide improved bounds on the DP-chromatic number of certain families of graphs. We will introduce two new analogues of the degeneracy of a graph to the fractional context, each of which bound its fractional DP-chromatic number from above. We will use these analogues to provide the best known upper bound on the fractional DP-chromatic number of a variety of graphs including unicyclic graphs, some complete bipartite graphs, and some sparse graphs.
This is joint work with Jeff Mudrock.
Discrete Applied Math Seminar