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

MaRDI QIDQ6403974zbMATH OpenFDO

Authors Hortensia Galeana-Sánchez, Felipe Hernández-Lorenzana, Rocio Sanchez-Lopez

Publication date 4 July 2022

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

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)longrightarrowV(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.

This page was built for publication: Cycles of length 3 and 4 in edge-colored complete graphs with restrictions in the color transitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6403974)