Extremal Problems on Graph-Referential Colorings of Graphs

Abstract

Suppose that G and H are 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 ∈ V in G. This definition descends from a question posed by Steve Hedetniemi, and opens the way to new, interesting questions regarding graph colorability. In this paper, we consider mainly extremal problems associated with this definition, exploring 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.