Atlantic Graph Theory Seminar: John Engbers (Marquette University)

Extremal questions for vertex colorings of graphs

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 endvertex, 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.

Join Zoom Meeting: link