pith. sign in

arxiv: 1701.08220 · v1 · pith:GR6ZFJDKnew · submitted 2017-01-27 · 🧮 math.CO

Transversals in generalized Latin squares

classification 🧮 math.CO
keywords generalizedlatinmulticoloredadmitsedge-coloringeveryleastmatching
0
0 comments X
read the original abstract

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 $K_{n,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 $K_{n,n}$, which contains at least $l(n)$ different colors, admits a multicolored perfect matching. They conjectured that $l(n)\leq n^2/2$ if $n$ is large enough. In this note we prove that $l(n)$ is bounded from above by $0.75n^2$ 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 $K_{2n}$ admits a multicolored $1$-factor.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.