On a problem of R. Häggkvist concerning edge-colouring of bipartite graphs (Q705747): Difference between revisions

This short note answers a question concerning an old problem of Häggkvist. Let \(L(n, K_{n, n})\) be the minimum of \(L(q)\), where \(L(q)\) stands for the maximal length of cycles colored by two colors in a proper edge-coloring of \(K_{n, n}\). It was known before that \(L(n, K_{n, n})\) can be as great as \(2n\) (for \(n=2, 3, 5\)), and strictly less then \(2n\) (for \(n=2^k\), it is equal to 4), see \textit{B. Zelinka} [Cas. Pest. Mat. 103, 289--290 (1978; Zbl 0391.05027)], or \(L(n, K_{n, n}) \leq n\) for every even \(n \geq 4\), see \textit{V. K. Bulitko} and \textit{J. Ninčák} [Math. Slovaca 38, No. 1, 11--17 (1988; Zbl 0672.05032)]. Here some of that old results are proved in a simpler way, and it is shown that indeed, except for the cases \(n=2, 3, 5\), \(L(n, K_{n, n}) < 2n\).