Faculty of Mathematics, Physics
and Informatics
Comenius University Bratislava

Seminar of Graph Theory - Gloria Tabarelli (12.5.2022)

Thursday 12.5.2022 at 9:50, Lecture room M/213


10. 05. 2022 13.06 hod.
By: Martin Škoviera

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 

More information