Loading Events

« All Events

Virtual Event Virtual Event
  • This event has passed.

A Polynomial Method for Counting Colorings of S-labeled Graphs

Mar. 4 @ 12:30 p.m. - 1:30 p.m.

Virtual Event Virtual Event
Free

The notion of S-labeling is a common generalization of classical vertex coloring, signed k-coloring, DP-coloring, group coloring, and coloring of gained graphs that was introduced in 2019 by Jin, Wong, and Zhu.

In this talk, we will show a polynomial method for bounding the number of colorings of S-labeled graphs from below. Our method uses a simple enumerative version of the Combinatorial Nullstellensatz discovered by Alon and Füredi in 1993. We also demonstrate how our method can be used to give new lower bounds on the DP color function, and consequently chromatic polynomial, of families of planar graphs, and the number of colorings of signed graphs. The lower bounds we will present improve previously known results or are the first such known results.

This is joint work with Hemanshu Kaul and Samantha Dahlberg.

Please contact mathstats-staff@ucdenver.edu to get Zoom URL.