Discrete Math Seminar by John Engbers: Extremal Questions for Vertex Colorings of Graphs

Speaker: John Engbers, University of Wisconsin-Milwaukee

Title: Extremal Questions for Vertex Colorings of Graphs

Abstract: For graphs $G$ and $H$, an $H$-coloring of $G$ is a map from the vertices of $G$ to the vertices of $H$ so that an edge in $G$ is mapped to an edge in $H$. The graph $H$ can be thought of as the allowable coloring scheme: its vertices are the colors used and its edges indicating colors that can appear on the endpoints of an edge in $G$. When the graph $H$ is the complete graph $K_q$, an $H$-coloring corresponds to a proper vertex coloring of $G$ with $q$ colors; when $H$ is an edge with one looped end vertex, an $H$-coloring corresponds to an independent set in $G$. After familiarizing ourselves with the notion of an $H$-coloring, we will consider the following extremal graph theory question: given a family of graphs and an $H$, which graph in the family has the most number of $H$-colorings, and which has the least number of $H$-colorings? We will discuss some things that are known (and not known!) in a variety of families, including trees and graphs with a fixed minimum degree.

Organizers: Hemanshu Kaul (kaul@iit.edu) and Samantha Dahlberg (sdahlberg@iit.edu)

Online Seminar: contact organizers for Zoom details or to join the mailing list.

 

Discrete Applied Math Seminar

Request Zoom Link