Department of Mathematics

Combinatorics and Graph Theory

  •  Hemanshu Kaul, Illinois Institute of Technology
  •  Polynomials and DP-coloring of Graphs
  •  02/22/2023
  •  3:00 PM - 3:50 PM
  •  Online (virtual meeting) (Virtual Meeting Link)
  •  Bruce E Sagan (

DP-coloring (also called correspondence coloring) of graphs is a generalization of list coloring of graphs that has been widely studied in recent years after its introduction by Dvorak and Postle in 2015. Intuitively, DP-coloring is a variation on list coloring where each vertex in the graph still gets a list of colors, but identification of which colors are different can change from edge to edge. DP-coloring has been investigated from both the extremal (DP-chromatic number) and the enumerative (DP-color function) perspectives. In this talk, we will give an overview of questions arising with regard to when the DP-color function equals the chromatic polynomial (or any polynomial), and how the polynomial method, through the Combinatorial Nullstellensatz and the Alon-Furedi theorem for the number of non-zeros of a polynomial, can be applied to both extremal and enumerative problems in DP-coloring. Many open problems and conjectures will be presented.



Department of Mathematics
Michigan State University
619 Red Cedar Road
C212 Wells Hall
East Lansing, MI 48824

Phone: (517) 353-0844
Fax: (517) 432-1562

College of Natural Science