Monochromatic Paths in 2-Edge-Coloured Graphs and Hypergraphs

[摘要] We answer a question of Gyárfás and Sárközy from 2013 by showing that every 2-edge-coloured complete 3-uniform hypergraph can be partitioned into two monochromatic tight paths of different colours. We also give a lower bound for the number of tight paths needed to partition any 2-edge-coloured complete k-partite k-uniform hypergraph. Finally, we show that any 2-edge coloured complete bipartite graph has a partition into a monochromatic cycle and a monochromatic path, of different colours, unless the colouring is a split colouring.

[学科分类] 统计和概率