2017/01/27 by János Barát, Zoltán Lóránt Nagy, Barát, János +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · doi:10.48550/arxiv.1701.08220
openalex publication_date 2017/01/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We are seeking a sufficient condition that forces a transversal in a generalized Latin square. A generalized Latin square of order n is equivalent to a proper edge-coloring of Kn,n. A transversal corresponds to a multicolored perfect matching. Akbari and Alipour defined l(n) as the least integer such that every properly edge-colored Kn,n, which contains at least l(n) different colors, admits a multicolored perfect matching. They conjectured that l(n)≤ n2/2 if n is large enough. In this note we prove that l(n) is bounded from above by 0.75n2 if n>1. We point out a connection to anti-Ramsey problems. We propose a conjecture related to a well-known result by Woolbright and Fu, that every proper edge-coloring of K2n admits a multicolored 1-factor.