Seminars

View all Seminars  |  Download ICal for this event

A Polynomial Method for Counting Colorings of Sparse Graphs

Series: Department Seminar

Speaker: Prof. Himanshu Kaul, Associate Professor of Applied Mathematics, Illinois Institute of Technology

Date/Time: Jun 16 15:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Abstract:
Conjectures and results related to the number of colorings of families of planar graphs have a long history. In this talk we give an overview of this history and our results that generalize this from two perspectives - more general notions of colorings and more general families of sparse graphs.

The notion of S-labeling, where S is a subset of the symmetric group, is a common generalization of signed k-coloring, signed Z_k-coloring, DP-coloring, group coloring, and coloring of gained graphs that was introduced in 2019 by Jin, Wong, and Zhu. We present a unified and simple polynomial method for giving exponential lower bounds on the number of colorings of a sparse S-labeled graph.
We apply these to give exponential lower bounds on the number of DP-colorings (and consequently, number of list colorings, and usual colorings) of families of planar graphs, and on the number of colorings of signed graphs. These lower bounds either improve previously known results, or are first known such results.

This is joint work with Samantha Dahlberg and Jeffrey.

Link

Host Faculty: Prof. Sunil Chandran L