TY - JOUR
T1 - Properly colored even cycles in edge-colored complete balanced bipartite graphs
AU - Guo, Shanshan
AU - Huang, Fei
AU - Yuan, J. J.
AU - Ng, Chi To
AU - Cheng, Tai Chiu Edwin
PY - 2025
Y1 - 2025
N2 - Consider a complete balanced bipartite graph K_{n,n} and let K^c_{n,n} be an edge-colored version of K_{n,n} that is obtained from K_{n,n} by having each edge assigned a certain color. A subgraph H of K_{n,n} is called properly colored (PC) if every two adjacent edges of H have distinct colors. K_{n,n} is called properly vertex-even-pancyclic if for every vertex u \in V(K_{n,n}) and for every even integer k with 4 <= k <= 2n, there exists a PC k-cycle containing u. The minimum color degree \delta^c (K^c_{n,n}) of K^c_{n,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 K^c_{n,n}. We first show that, for every integer t >= 3, every K^c_{n,n} with \delta^c (K^c_{n,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 \epsilon > 0, there exists an integer n_0(\epsilon) such that every K^c_{n,n} with n >= n_0(\epsilon) is properly vertex-even-pancyclic, provided that \delta^c (K^c_{n,n}) >= (2/3 + \epsilon)n.
AB - Consider a complete balanced bipartite graph K_{n,n} and let K^c_{n,n} be an edge-colored version of K_{n,n} that is obtained from K_{n,n} by having each edge assigned a certain color. A subgraph H of K_{n,n} is called properly colored (PC) if every two adjacent edges of H have distinct colors. K_{n,n} is called properly vertex-even-pancyclic if for every vertex u \in V(K_{n,n}) and for every even integer k with 4 <= k <= 2n, there exists a PC k-cycle containing u. The minimum color degree \delta^c (K^c_{n,n}) of K^c_{n,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 K^c_{n,n}. We first show that, for every integer t >= 3, every K^c_{n,n} with \delta^c (K^c_{n,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 \epsilon > 0, there exists an integer n_0(\epsilon) such that every K^c_{n,n} with n >= n_0(\epsilon) is properly vertex-even-pancyclic, provided that \delta^c (K^c_{n,n}) >= (2/3 + \epsilon)n.
KW - Edge-coloring
KW - Properly colored cycle
KW - Properly colored 2-factor
KW - Vertex-even-pancyclic
KW - Color degree
UR - https://doi.org/10.1016/j.disc.2025.114575
M3 - Journal article
SN - 0012-365X
VL - 348
JO - Discrete Mathematics
JF - Discrete Mathematics
M1 - 114575
ER -