Interesting Properties of DP-Coloring

When:

Mar 5, 2018 - 1:50pm to 2:55pm

Where:

Rettaliata Engineering Center, Room 104

Speaker:

Alexandr Kostochka
Department of Mathematics, University of Illinois at Urbana-Champaign

Description:

Dvořák and Postle introduced DP-coloring to answer a question of Borodin on list-coloring of planar graphs. Formally, a DP-$$k$$-coloring of a graph $$G$$ is not exactly a coloring, but is an independent set in an auxiliary graph $$H(G,k)$$. However, DP-coloring has many properties of ordinary and list colorings. A number of known bounds on the list chromatic number of graphs also hold for the DP-chromatic number. On the other hand, some properties of DP-coloring significantly differ from those of list coloring.

The goal of the talk is to discuss the concept and properties of DP-coloring of graphs and to point out possible directions of studying this parameter.

The talk is based on joint work with A. Bernshteyn, S. Pron and X. Zhu.

Event Type:

Department of Applied Mathematics - Colloquia