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.