Interesting Properties of DP-Coloring

-
Rettaliata Engineering Center, Room 104
  1. Home
  2. Events
  3. Interesting Properties of DP-Coloring

Host

Department of Applied Mathematics

Speaker

Alexandr Kostochka
Department of Mathematics, University of Illinois at Urbana-Champaign
https://faculty.math.illinois.edu/~kostochk/



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.

Tags: