DMS Combinatorics Seminar

Speaker: Ariel Cook (Auburn University)

Graph-Referential List-Colorings of Graphs 

Abstract: Let $G$ and $H$ be finite, simple graphs on the same vertex set $V$.  A (proper) $G$-coloring of (H\) is a (proper) list-coloring of $H$ from the lists $N_G(v)$, the open neighborhood of $v\in V(G)$. This definition descends from a question posed by Steve Hedetniemi, and opens the way to new, interesting questions regarding graph colorability. Our current research focuses on extremal problems associated with this definition, including maximal graphs $H$ such that $H$ is $G$-colorable, minimal graphs $H$ such that $H$ is not $G$-colorable, minimal graphs $G$ such that $H$ is $G$-colorable, and maximal graphs $G$ such that $H$ is not $G$-colorable.