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 language | English |
|---|---|
| Article number | 114575 |
| Journal | Discrete Mathematics |
| Volume | 348 |
| Issue number | 11 |
| DOIs | |
| Publication status | Published - 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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver