Seminar of Graph Theory - Gloria Tabarelli (12.5.2022)
Thursday 12.5.2022 at 9:50, Lecture room M/213
Gloria Tabarelli (University of Verona):
H-colorings in cubic and r-regular graphs
Abstract:
Let H and G be graphs: an H-coloring of G is a map f : E(G) → E(H) such that for any vertex v ∈ V (G) there exists a unique vertex u ∈ V (H) with f(∂G(v)) = ∂H(u), where ∂G(v) denotes the set of edges incident to the vertex v in the graph G. If G admits an H-coloring we say that H colors G. It has been shown that if the Petersen-coloring conjecture is true, the Petersen graph is the unique connected bridgeless cubic graph which can color all the bridgeless cubic graphs. In this seminar we survey some known results on H-colorings of graphs, considering several different assumptions on H and G, and provide some new results concerning uniqueness of H in the above sense