DMS Discrete Mathematics Seminar

Speaker: Ariel Cook

Title: Colorings of Graphs with Reference to Other Graphs

Abstract: Suppose that G and H are (finite, simple) graphs on the same vertex set V. A (proper) G-coloring of H is an assignment to each vertex v of an element of NG(v) so that vertices adjacent in H are assigned different vertices. A G-coloring of G is a self-coloring of G. A Gc-coloring of G is an anti-self-coloring of G. Numerous questions arise, some of which will be reported on in this talk. These questions all descend from an ancestral question, posed by Steve Hedetniemi: For which graphs G does the indexed family of open neighborhoods in G of G’s vertices have a system of distinct representatives? Clearly, such an SDR would constitute a G-coloring of the complete graph on V(G). Hedetniemi’s question was satisfactorily answered in 2018, by Hedetniemi, Holliday, and Johnson, but its position in the wider context introduced here was not realized until recently.

This is joint work with Sarah Holliday and Peter Johnson.