A generalization of properly colored paths and cycles in edge-colored graphs

• Published in: Theoretical computer science 2023-02, Vol.946, p.113679, Article 113679
• Main Authors: Galeana-Sánchez, Hortensia, Hernández-Lorenzana, Felipe, Sánchez-López, Rocío
• Format: Article
• Language: English
• Subjects: Edge-colored graph; H-cycle; H-path; Properly colored walk
• ISSN: 0304-3975
• DOI: 10.1016/j.tcs.2022.12.029

A properly colored walk, is a walk where every two consecutive edges have different colors, including the first and last edges in the case when the walk is closed. Properly colored walks have shown to be an effective way to model certain real applications. In view of this, it is natural to ask about the existence of properly colored walks with restrictions on the transitions of colors allowed in the edges of a graph. Let H be a graph, possibly with loops, and G a graph. We will say that G is H-colored iff there exists a function c:E(G)⟶V(H). A path (v0,v1,⋯,vk) in G is an H-path whenever (c(v0v1),⋯,c(vk−1vk)) is a walk in H; in particular, a cycle (v0,v1,⋯,vk,v0) is an H-cycle iff (c(v0v1),c(v1v2),⋯,c(vk−1vk),c(vkv0),c(v0v1)) is a walk in H. Hence, the graph H determines what color transitions are allowed in a walk. An interesting application of H-walks states as follows: suppose that it is required to send a message through a hostile environment (network), in which the edges are colored with its transmission code; in order to make more difficult the decoding task, it is necessary to avoid not only monochromatic transitions, but some specific color transitions that make easier that task. Some authors have studied the existence of H-cycles in an H-colored graph, saying nothing about its length. In this paper, we give conditions that imply the existence of H-paths and H-cycles of certain length, in an H-colored graph with a given structure. As a consequence of the main results, we obtain known theorems in the theory of properly colored walks.