On a problem of R. Häggkvist concerning edge-colouring of bipartite graphs
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\).
- Linear spaces with small generated subspaces
- scientific article; zbMATH DE number 3933100 (Why is no real title available?)
- scientific article; zbMATH DE number 4099331 (Why is no real title available?)
- Cycles of quadratic Latin squares and antiperfect 1‐factorisations
- Small antiperfect Steiner triple systems
- Edge-colourings of \(K_{n,n}\) with no long two-coloured cycles
This page was built for publication: On a problem of R. Häggkvist concerning edge-colouring of bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705747)
