Close Menu

Interesting Properties of DP-Coloring


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


Rettaliata Engineering Center, Room 104


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


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