Cycles of length 3 and 4 in edge-colored complete graphs with restrictions in the color transitions

Abstract

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)⟶V(H)$. A path $(v_1,\cdots ,v_k)$ in $G$ is an $H$-path whenever $(c(v_1{v}_2),\cdots ,$ $c(v_{k-1}{v}_k))$ is a walk in $H$, in particular, a cycle $(v_1,\cdots ,v_k,v_1)$ is an $H$-cycle iff $(c(v_1{v}_2),\cdots ,c(v_{k-1}{v}_k),$ $c(v_k{v}_1),c(v_1{v}_2))$ 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.

19 pages, 3 figures