2023/10/08 by Guo, Shanshan, Huang, Fei, Yuan, Jinjiang +2
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2310.04962
Consider a complete balanced bipartite graph Kn,n and let Kcn,n be an edge-colored version of Kn,n that is obtained from Kn,n by having each edge assigned a certain color. A subgraph H of Kcn,n is called properly colored (PC) if every two adjacent edges of H have distinct colors. Kn,nc is called properly vertex-even-pancyclic if for every vertex u∈ V(Kn,nc) and for every even integer k with 4 ≤ k ≤ 2n, there exists a PC k-cycle containing u. The minimum color degree δc(Kcn,n) of Kcn,n is the largest integer k such that for every vertex v, there are at least k distinct colors on the edges incident to v. In this paper we study the existence of PC even cycles in Kn,nc. We first show that, for every integer t≥ 3, every Kcn,n with δc(Kcn,n)≥ (2n)/(3)+t contains a PC 2-factor H such that every cycle of H has a length of at least t. By using the probabilistic method and absorbing technique, we use the above result to further show that, for every ε>0, there exists an integer n0(ε) such that every Kcn,n with n≥ n0(ε) is properly vertex-even-pancyclic, provided that δc(Kcn,n)≥ ((2)/(3)+ε)n.