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

Let G be a graph and H a graph possibly with loops. We will say that a graph G is an H -colored graph if and only if there exists a function c : E ( G ) ⟶ V ( H ) . A cycle ( v 1 , … , v k , v 1 ) is an H -cycle if and only if ( c ( v 1 v 2 ) , … , c ( v k - 1 v k ) , c ( v k v 1 ) , c ( v 1 v 2 ) )...

Full description

Saved in:
Bibliographic Details
Published in:Boletín de la Sociedad Matemática Mexicana 2024-11, Vol.30 (3), Article 72
Main Authors: Galeana-Sánchez, Hortensia, Hernández-Lorenzana, Felipe, Sánchez-López, Rocío
Format: Article
Language:English
Subjects:
Graph coloring
Mathematics
Mathematics and Statistics
Original Article
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G be a graph and H a graph possibly with loops. We will say that a graph G is an H -colored graph if and only if there exists a function c : E ( G ) ⟶ V ( H ) . A cycle ( v 1 , … , v k , v 1 ) is an H -cycle if and only if ( c ( v 1 v 2 ) , … , c ( v k - 1 v k ) , c ( v k v 1 ) , c ( v 1 v 2 ) ) is a walk in H . Whenever H is a complete graph without loops, an H -cycle is a properly colored cycle. In this paper, we work with an H -colored complete graph, namely G , with local restrictions given by an auxiliary graph, and we show sufficient conditions implying that every vertex in V ( G ) is contained in an H -cycle of length 3 (respectively 4). As a consequence, we obtain some well-known results in the theory of properly colored walks.
ISSN:1405-213X
2296-4495
DOI:10.1007/s40590-024-00645-0