×

zbMATH — the first resource for mathematics

On a problem of R. Häggkvist concerning the edge colourings of bipartite graphs. (English) Zbl 0583.05026
In an n-edge-colouring q of the complete bipartite graph \(K_{n,n}\), let L(q) be the maximum length of a 2-coloured cycle. Let \(L(n,K_{n,n})\) be the minimum value of L(q) taken over all such n-edge-colourings. R. Häggkvist [pp. 1203-1204 of problems section, Combinatorics, Keszthely 1976, Colloq. Math. Soc. János Bolyai 18, 1189-1220 (1978; Zbl 0379.05001)] asked whether \(L(n,K_{n,n})=2n\) and B. Zelinka [Čas. Pěstovani Mat. 103, 289-290 (1978; Zbl 0391.05027)] proved that \(L(n,K_{n,n})=4\) if \(n=2^ k\) and \(k\geq 1\). The purpose of this paper is to prove that \(L(n,K_{n,n})\leq n\) if n is even and exceeds 2. The case of odd n will be treated elsewhere.
Reviewer: J.G.Oxley
MSC:
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite