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