Partitioning edge-coloured infinite complete bipartite graphs into monochromatic paths

DOI10.1007/S11856-020-2030-ZzbMATH Open1447.05168arXiv1808.09836OpenAlexW3033580797MaRDI QIDQ2200044FDOQ2200044

Authors: Carl Bürger, Max F. Pitz 

Publication date: 15 September 2020

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Abstract: In 1978, Richard Rado showed that every edge-coloured complete graph of countably infinite order can be partitioned into monochromatic paths of different colours. He asked whether this remains true for uncountable complete graphs and a notion of emph{generalised paths}. In 2016, Daniel Soukup answered this in the affirmative and conjectured that a similar result should hold for complete bipartite graphs with bipartition classes of the same infinite cardinality, namely that every such graph edge-coloured with $r$ colours can be partitioned into $2r-1$ monochromatic generalised paths with each colour being used at most twice. In the present paper, we give an affirmative answer to Soukup's conjecture.

Full work available at URL: https://arxiv.org/abs/1808.09836

Recommendations

• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Partitioning 2-edge-colored complete multipartite graphs into monochromatic cycles, paths and trees
• Decompositions of edge-colored infinite complete graphs into monochromatic paths
• Partitioning 2-edge-colored graphs by monochromatic paths and cycles
• Partitioning infinite hypergraphs into few monochromatic Berge-paths
• Partitioning complete bipartite graphs by monochromatic cycles
• Decompositions of edge-coloured infinite complete graphs into monochromatic paths. II
• Partitioning 3-edge-coloured complete bipartite graphs into monochromatic cycles

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• Decompositions of edge-colored infinite complete graphs into monochromatic paths
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Graph theory
• Monochromatic Paths in Graphs
• Decompositions of edge-coloured infinite complete graphs into monochromatic paths. II

Cited In (6)

• Partitioning edge-coloured complete symmetric digraphs into monochromatic complete subgraphs
• Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
• Decompositions of edge-coloured infinite complete graphs into monochromatic paths. II
• Partitioning infinite hypergraphs into few monochromatic Berge-paths
• Decompositions of edge-colored infinite complete graphs into monochromatic paths
• Applications of Order Trees in Infinite Graphs

This page was built for publication: Partitioning edge-coloured infinite complete bipartite graphs into monochromatic paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200044)