Partitioning edge-coloured infinite complete bipartite graphs into monochromatic paths

DOI10.1007/S11856-020-2030-ZMaRDI QIDQ2200044zbMATH OpenOpenAlexFDO

Authors Carl Bürger, Max F. Pitz

Publication date 15 September 2020

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

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

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)

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.

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

Cites work

• Decompositions of edge-colored infinite complete graphs into monochromatic paths
• Decompositions of edge-coloured infinite complete graphs into monochromatic paths. II
• Graph theory
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• Monochromatic Paths in Graphs
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths

Cited in

(6)

• Decompositions of edge-coloured infinite complete graphs into monochromatic paths. II
• Partitioning edge-coloured complete symmetric digraphs into monochromatic complete subgraphs
• Partitioning infinite hypergraphs into few monochromatic Berge-paths
• Decompositions of edge-colored infinite complete graphs into monochromatic paths
• Ore- and Pósa-type conditions for partitioning 2-edge-coloured graphs into monochromatic cycles
• 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)