Seminár z teórie grafov - Gloria Tabarelli (12.5.2022)
vo štvrtok 12.5.2022 o 9:50 hod. v miestnosti M/213
Od: Martin Škoviera
Prednášajúci: Gloria Tabarelli (University of Verona)
Názov: H-colorings in cubic and r-regular graphs
Termín: 12.5.2022, 9:50 hod., M 213
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.