Partitioning edge-coloured infinite complete bipartite graphs into monochromatic paths
- PDF / 428,183 Bytes
- 22 Pages / 429.41 x 636.77 pts Page_size
- 98 Downloads / 225 Views
PARTITIONING EDGE-COLOURED INFINITE COMPLETE BIPARTITE GRAPHS INTO MONOCHROMATIC PATHS
BY
¨ rger and Max Pitz Carl Bu Department of Mathematics, University of Hamburg, Bundesstraße 55 (Geomatikum), 20146 Hamburg, Germany e-mail: [email protected], [email protected]
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 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.
1. Introduction Throughout this paper, the term colouring always refers to edge colourings of graphs with finitely many colours. In the 1970s, Erd˝ os proved (unpublished) that every 2-coloured complete graph of countably infinite order, i.e., every 2-coloured Kℵ0 , can be partitioned into monochromatic paths of different colours, where ‘path’ means either a finite path or a one-way infinite ray. Rado subsequently extended Erd˝os result to any finite number of colours [6, Theorem 2]. Received August 29, 2018 and in revised form July 12, 2019
1
2
¨ C. BURGER AND M. PITZ
Isr. J. Math.
In the same paper, Rado then asked whether a similar result holds for all infinite complete graphs, even the uncountable ones. Clearly, it is not possible to partition such a graph into finitely many ‘usual’ paths, as graph-theoretic paths and rays are inherently countable. Hence, Rado introduced the following notion of generalised path: A generalised path is a graph P together with a well-order ≺ on V (P ) (called the path order on P ) satisfying that the set {w ∈ N (v) : w ≺ v} of down-neighbours of v is cofinal below v for every vertex v ∈ V (P ), i.e., for every v 0 ≺ v there is a neighbour w of v with v 0 w ≺ v (see Figure 1).
Figure 1. A generalised path. In particular, every successor element is adjacent to its predecessor in the well-order. Calling such a graph P a ‘generalised path’ is justified by the fact that between any two vertices v ≺ w of P there exists a finite path from v to w strictly increasing with respect to ≺; see, e.g., [3, Observation 5.2]. If the situation is clear, we write P instead of (P, ≺) and treat P as a graph. By Λ(P, ≺) = Λ(P ) we denote the limit elements of the well-order (P, ≺). When the situation is clear, we sometimes write Λ instead of Λ(P ). If necessary, the path-order ≺ on V (P ) will be referred to as ≺P . If v, v 0 ∈ P , then we denote by (v, v 0 ) and [v, v 0 ] the open and closed intervals with respect to ≺, and by [v, v + ω) the ray of P starting at v compatible with the path order. Note that a one-way in
Data Loading...
