Skip to main navigation Skip to search Skip to main content

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

Consider a complete balanced bipartite graph K n,n and let K n,n c 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 c is called properly colored (PC) if every two adjacent edges of H have distinct colors. K n,n c is called properly vertex-even-pancyclic if for every vertex u∈V(K n,n c) and for every even integer k with 4≤k≤2n, there exists a PC k-cycle containing u. The minimum color degree δ c(K n,n c) of K n,n c 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 n,n c. We first show that, for every integer t≥3, every K n,n c with δ c(K n,n c)≥[Formula presented]+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 n 0(ε) such that every K n,n c with n≥n 0(ε) is properly vertex-even-pancyclic, provided that δ c(K n,n c)≥([Formula presented]+ε)n.

Original languageEnglish
Article number114575
JournalDiscrete Mathematics
Volume348
Issue number11
DOIs
Publication statusPublished - Nov 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