Properly colored even cycles in edge-colored complete balanced bipartite graphs

Shanshan Guo, Fei Huang, J. J. Yuan, Chi To Ng, Tai Chiu Edwin Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

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.
Original languageEnglish
Article number114575
JournalDiscrete Mathematics
Volume348
Publication statusPublished - 2025

Keywords

  • Edge-coloring
  • Properly colored cycle
  • Properly colored 2-factor
  • Vertex-even-pancyclic
  • Color degree

Fingerprint

Dive into the research topics of 'Properly colored even cycles in edge-colored complete balanced bipartite graphs'. Together they form a unique fingerprint.

Cite this