• This event has passed.

# Atlantic Graph Theory Seminar: John Engbers (Marquette University)

## April 6, 2022 @ 3:30 pm - 4:30 pm

### 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.

## Details

Date:
April 6, 2022
Time:
3:30 pm - 4:30 pm
Event Category:
Website:
https://math.us7.list-manage.com/track/click?u=36f9a23be2975bac073fd4379&id=526a09392a&e=2b807e4035

Zoom seminar

## Organizer

Jason Brown
Phone:
9024947063
Email:
jason.brown@dal.ca