2022/07/04 by Galeana-Sánchez, Hortensia, Hernández-Lorenzana, Felipe, Sánchez-López, Rocío
#05C07 #05C15 #05C38 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2207.01699
Let G be an edge-colored graph, a walk in G is said to be a properly colored walk iff each pair of consecutive edges have different colors, including the first and the last edges in case that the walk be closed. Let H be a graph possible with loops. We will say that a graph G is an H-colored graph iff there exists a function c:E(G)\longrightarrow V(H). A path (v1,⋯,vk) in G is an H-path whenever (c(v1v2),⋯, c(vk-1vk)) is a walk in H, in particular, a cycle (v1,⋯,vk,v1) is an H-cycle iff (c(v1 v2),⋯,c(vk-1vk), c(vkv1), c(v1 v2)) is a walk in H. Hence, H decide which color transitions are allowed in a walk, in order to be an H-walk. Whenever H is a complete graph without loops, an H-walk is a properly colored walk, so H-walk is a more general concept. In this paper, we work with H-colored complete graphs, with restrictions given by an auxiliary graph. The main theorems give conditions implying that every vertex in an H-colored complete graph, is contained in an H-cycle of length 3 and in an H-cycle of length 4. As a consequence of the main results, we obtain some well-known theorems in the theory of properly colored walks.