PARTITIONING BY MONOCHROMATIC TREES

P.E. Haxell and Y. Kohayakawa

Abstract. Any r-edge-coloured n-vertex complete graph K^{n} contains at most r monochromatic trees, all of different colours, whose vertex sets partition the vertex set of K^{n}, provided n ≥ 3r^{4}r!(1 − 1/r)^{3(1−r)} log r. This comes close to proving, for large n, a conjecture of Erdős, Gyárfás, and Pyber, which states that r − 1 trees suffice for all n.

§1. Introduction

The tree partition number of r-edge-coloured complete graphs is defined to be the minimum k such that whenever the edges of a complete graph K^{n} are coloured with r colours, the vertices of K^{n} can be covered by at most k vertex-disjoint monochromatic trees. The cycle partition number is defined similarly. Erdős, Gyárfás, and Pyber [1] proved that the cycle partition number (and hence the tree partition number) is at most cr^{2} log r for some constant c. They conjectured in [1] that the cycle partition number is r, and that the tree partition number is r − 1. Here we prove that the tree partition number is at most r provided n is sufficiently large with respect to r. Our main theorem, the proof of which is postponed until the next section, is as follows.

Theorem 1. Let r ≥ 1 and n ≥ 3r^{4}r!(1 − 1/r)^{3(1−r)} log r be integers, and suppose the edges of K^{n} are coloured with r colours. Then K^{n} contains t ≤ r monochromatic trees T_{1}, …, T_{t} of radius at most 2, each of a different colour, such that their vertex sets V (T_{i}) (1 ≤ i ≤ t) partition the vertex set of K^{n}.

Note that the lower bound for n above is, for large r, about 3e^{3}r^{4}r! log r. As shown in [1], the conjecture for tree partitions is best possible, if true, when r − 1 is a prime power. To see this, let n = (r − 1)^{2}, and let K^{n} be a complete graph whose vertices are labelled with the points of an affine plane of order r − 1. Let a colouring of the edges of K^{n} be given by assigning colour i to the edge xy if the line through x and y is in the ith parallel class. Then each monochromatic component of this colouring is a complete subgraph of order r − 1, and so at least r − 1 monochromatic trees would be required to partition the set of vertices. This example can be extended to an example for any n ≥ (r − 1)^{2}(r − 2), by replacing each vertex x of K^{(r−1)^{2}} with a set of vertices X of size ⌊n/(r−1)^{2}⌋ or ⌈n/(r−1)^{2}⌉.

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 05C05, 05C35, 05C40; Secondary 05D10.

Key words and phrases. Trees, partitioning of graphs, monochromatic subgraphs.

The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603–1) and by CNPq (Proc. 300334/93–1 and ProTeM-CC-II Project ProComb).

Then edge zw for z ∈ Z, w ∈ W is given colour i if Z ≠ W and the line through Z and W is in the ith parallel class, and colour 1 if Z = W. Then the monochromatic components of this colouring each have at most (r − 1)⌈n/(r − 1)^{2}⌉ < n/(r − 2) vertices, and hence any tree partition would require at least r − 1 trees.

The tree partition conjecture for r = 2 is equivalent to the fact that either a graph or its complement is connected, an old remark of Erdős and Rado. For r = 3 the conjecture was proved by Erdős, Gyárfás, and Pyber [1]. It was proved by Hajnal (see [4]) that the tree partition number for r-edge-coloured infinite complete graphs is at most r. Rado [5] proved that an r-edge-coloured countably infinite complete graph may be partitioned into r monochromatic, possibly one-way infinite, paths, generalising a result of Erdős, who had proved this statement for r = 2.

A problem that is related to tree partitioning is finding the tree cover number for r-edge-coloured complete graphs, the minimum number k such that the vertices of an r-edge-coloured complete graph can be covered by k (not necessarily disjoint) monochromatic trees. It is clear that this number is at most r, as the set of monochromatic stars centred at any vertex give a cover, and in the example described previously it is at least r − 1. As shown by Gyárfás [3], proving that the tree cover number is r −1 is equivalent to proving a conjecture of Lovász and Ryser (see, e.g. Füredi [2]), which states that an r-partite intersecting hypergraph has a transversal of size at most r − 1. This was proved by Tuza for r ≤ 5 in [6].

§2. Proof of Theorem 1

Let integers r and n as in the statement of the theorem be given. We may assume that r ≥ 4. Suppose the edges of K^{n} have been coloured with colours from [r] = {1, …, r}.

We start with some definitions. Let s_{1} = ⌈(n − 1)/r⌉, and define the integers s_{i} (2 ≤ i ≤ r) by letting

s_{i} = ⌊\frac{1}{r − i + 1} (1 − \frac{1}{r})^{2} s_{i−1}⌋ .  (1)

It is clear that the s_{i} form a non-increasing sequence. A straightforward but somewhat tedious calculation shows that s_{r} ≥ r^{3} log n, since n is assumed to be sufficiently large with respect to r. (Throughout this note, log will denote the natural logarithm.)

Let B be a complete bipartite subgraph of our K^{n} with a specified bipartition V (B) = X ∪Y. Suppose that X = {x_{1}, …, x_{t}}, where 1 ≤ t ≤ r, and |Y | ≥ s_{t}. We say that B is an anchor graph if the colouring of K^{n} is such that the colour of the edge x_{i}y (y ∈ Y) depends only on x_{i}, and this colour is distinct for each x_{i} (1 ≤ i ≤ t). We refer to t as the index of B. Thus, an anchor graph of index t is formed by t monochromatic stars in K^{n}, all of distinct colours, and with the same set of leaves.

Let 1 ≤ t ≤ r be the largest integer for which K^{n} contains an anchor graph of index t. Fix an anchor graph B ⊂ K^{n} of index t, and suppose without loss of generality that the edges x_{i}y (y ∈ Y) have colour i for all 1 ≤ i ≤ t.

For v ∈ K^{n}, U ⊂ V (K^{n}) \ {v}, and 1 ≤ i ≤ r, we let Γ_{i}(v, U) be the set of vertices from U that are joined to v by edges of colour i. Put d_{i}(v, U) = |Γ_{i}(v, U)|. Observe that, by the maximality of t, we have d_{i}(z, Y) < s_{t+1} for every z ∈ Z = V (K^{n}) \ V (B) and every t < i ≤ r.

We now use a simple greedy procedure to find a covering of Z by monochromatic stars with centres in Y. To be precise, suppose that, for some q ≥ 0, vertices y_{1}, …, y_{q} ∈ Y, colours i_{1}, …, i_{q} ∈ [t], and pairwise disjoint sets Z_{1}, …, Z_{q} ⊂ Z have been defined such that, for all 1 ≤ k ≤ q, we have

(i) Z_{k} ⊂ Γ_{i_{k}}(y_{k}, Z), (ii) putting Z′_{0} = Z and Z′_{k} = Z \ ⋃_{j=1}^{k} Z_{j}, for 1 ≤ k ≤ q we have

|Z′_{k}| ≤ |Z′_{k−1}| exp \{−\frac{1}{tr} \} .  (2)

If Z = ⋃_{k=1}^{q} Z_{k}, we have found the desired covering. Thus suppose that Z′_{q} = Z \ ⋃_{k=1}^{q} Z_{k} ≠ ∅. Condition (ii) applied recursively gives that

|Z′_{q}| ≤ |Z| exp{−q/tr} < ne^{−q/tr},

and hence, since Z′_{q} ≠ ∅, we deduce that q < tr log n. As observed above, s_{r} ≥ r^{3} log n, whence

s_{r} > rq.  (3)

Therefore Y′_{q} = Y \ {y_{1}, …, y_{q}} ≠ ∅ since |Y | ≥ s_{t} ≥ s_{r} > rq ≥ q. Now to continue the procedure, we let y_{q+1} and i_{q+1} be such that d_{i_{q+1}}(y_{q+1}, Z′_{q}) is maximal over all choices of y_{q+1} ∈ Y′_{q} ≠ ∅ and i_{q+1} ∈ [t]. Put Z_{q+1} = Γ_{i_{q+1}}(y_{q+1}, Z′_{q}). We now check that (i) and (ii) hold for k = q + 1. Clearly, the only work lies in checking (2). Let us first observe that the number of edges of colours 1, …, t between Y′_{q} and Z′_{q} is at least

∑_{z∈Z′_{q}} ∑_{1≤i≤t} d_{i}(z, Y′_{q}) ≥ |Z′_{q}|{|Y | − q − (r − t)s_{t+1}},

where s_{r+1} is taken to be 0. Thus

d_{i_{q+1}}(y_{q+1}, Z′_{q}) = max\{d_{i}(y, Z′_{q}): 1 ≤ i ≤ t, y ∈ Y′_{q}\} ≥ \frac{1}{t} (1 − \frac{(r − t)s_{t+1}}{|Y | − q} ) |Z′_{q}|.

Hence, putting Z′_{q+1} = Z \ ⋃_{k=1}^{q+1} Z_{k}, we have

|Z′_{q+1}| ≤ (1 − \frac{1}{t} (1 − \frac{(r − t)s_{t+1}}{|Y | − q} )) |Z′_{q}| ≤ |Z′_{q}| exp \{−\frac{1}{t} (1 − \frac{(r − t)s_{t+1}}{|Y | − q} )\} .

But 1 − (r − t)s_{t+1}/(|Y | − q) ≥ 1 − (r − t)s_{t+1}/(1 − 1/r)s_{t} ≥ 1/r, where the first inequality follows from (3) and the second follows from (1). Therefore |Z′_{q+1}| ≤ |Z′_{q}| exp{−1/tr}, as required.

The considerations above show that our procedure terminates with a covering of Z by monochromatic stars with centres y_{1}, …, y_{q_{0}}, colours i_{1}, …, i_{q_{0}}, and sets of leaves Z_{1}, …, Z_{q_{0}}. To complete our tree partition, we define trees T_{1}, …, T_{t} of colours 1, …, t as follows. The tree T_{i} (1 ≤ i ≤ t) has vertex set V (T_{i}) = {x_{i}} ∪ ⋃({y_{k}} ∪ Z_{k}) and edge set E(T_{i}) = ⋃({x_{i}y_{k}} ∪ {y_{k}z: z ∈ Z_{k}}), where the unions range over all k ∈ [q] with i_{k} = i. Clearly ⋃_{i=1}^{t} V (T_{i}) = X ∪ Y_{0} ∪ Z, where Y_{0} = {y_{1}, …, y_{q_{0}}}. It can be easily seen that the vertices in Y \ Y_{0} may be added to T_{1} as leaves to give a tree partition of K^{n} as required. This completes the proof of the theorem.

References

1. Erdős, P., Gyárfás, A., Pyber, L., Vertex coverings by monochromatic cycles and trees, J. Combinatorial Theory (B) 51 (1991), 90–95.

2. Füredi, Z., Matchings and covers in hypergraphs, Graphs and Combinatorics 4 (1988), 115– 206.

3. Gyárfás, A., Partition covers and blocking sets in hypergraphs, MTA SZTAKI Studies,Volume 71 (in Hungarian), 1977.

4. Hajnal, A., Komjáth, P., Soukup, L., Szalkai, I., Decompositions of edge coloured infinite complete graphs, Combinatorics: 7th Hungarian Colloquium, Eger 1987 (Hajnal, A., Lovász, L., Sós, V.T., eds.), Colloquia Mathematica Societatis János Bolyai, Vol 52, North-Holland, Amsterdam, 1988, pp. 277–280.

5. Rado, R., Monochromatic paths in graphs, Advances in Graph Theory (Bollobás, B., ed.), Annals of Discrete Mathematics 3, North-Holland, Amsterdam, 1978, pp. 191–194.

6. Tuza, Zs., Some special cases of Ryser’s conjecture (1978), preprint.

Department of Combinatorics and Optimisation, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

E-mail address: <pehaxell@math.uwaterloo.ca>

Instituto de Matemática e Estatística, Universidade de São Paulo, Cidade Universitária, Rua do Matão 1010, 05508–900 São Paulo, SP, Brazil

E-mail address: <yoshi@ime.usp.br>