Partitioning complete bipartite graphs by monochromatic cycles (Q1354726)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Partitioning complete bipartite graphs by monochromatic cycles |
scientific article |
Statements
Partitioning complete bipartite graphs by monochromatic cycles (English)
0 references
3 August 1997
0 references
For every positive integer \(r\) there exists a constant \(C_r\) depending only on \(r\) such that for every colouring of the edges of the complete bipartite graph \(K^{n,n}\) with \(r\) colours, there exists a set of at most \(C_r\) monochromatic cycles whose vertex sets partition the vertex set of \(K^{n,n}\). This answers a question raised by \textit{P. Erdös}, \textit{A. Gyárfás} and \textit{L. Pyber} [J. Comb. Theory, Ser. B 51, No. 1, 90-95 (1991; Zbl 0766.05062)].
0 references
colouring
0 references
complete bipartite graph
0 references
monochromatic cycles
0 references
partition
0 references