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