On a problem of R. Häggkvist concerning edge-colouring of bipartite graphs
type: Item
instance of: scholarly article
title: On a problem of R. Häggkvist concerning edge-colouring of bipartite graphs
zbMATH Open document ID: 1057.05037
author: Ján Ninčák
author: Peter J. Owens
published in: Combinatorica
publication date: 2005-02-14T00:00:00Z
review text: 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\).
reviewed by: András Pluhár
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05B15
zbMATH DE Number: 2133937
zbMATH Keywords: Häggkvist problem
zbMATH Keywords: Latin squares
zbMATH Keywords: edge-coloring
MaRDI profile type: Publication
full work available at URL: s00493-004-0020-0
OpenAlex ID: W2486502620
DOI: 10.1007/S00493-004-0020-0
description: scientific article; zbMATH DE number 2133937