Local colourings and monochromatic partitions in complete bipartite graphs

2015/01/22 by Richard Lang, Lang, Richard, Maya Stein +1 · 1 citation
Computer Science · Mathematics · #05C38 #05C55 #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1501.05619

openalex publication_date 2015/01/22 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

We show that for any 2-local colouring of the edges of the balanced complete bipartite graph K_n,n, its vertices can be covered with at most~3 disjoint monochromatic paths. And, we can cover almost all vertices of any complete or balanced complete bipartite r-locally coloured graph with O(r²) disjoint monochromatic cycles. We also determine the 2-local bipartite Ramsey number of a path almost exactly: Every 2-local colouring of the edges of K_n,n contains a monochromatic path on n vertices.

Cited by

• Monochromatic cycle partitions in 3-mean edge-colourings

Related

• Monochromatic cycle partitions in local edge colourings
• Partitioning 2-edge-coloured bipartite graphs into monochromatic cycles
• Partitioning two-coloured complete multipartite graphs into monochromatic paths and cycles
• Multicolour bipartite Ramsey number of paths
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths