Packing trees into n-chromatic graphs

Graphs, Hypergraphs, and Computing

01 April 15:30 - 16:30

Andras Gyarfas - Alfred Renyi Institute of Mathematics

In 1976, fascinated by 1+2+...+(n-1)=n(n-1)/2, I conjectured [3] that any sequence T_1,T_2,...,T_{n-1} of trees (T_i has i edges) can be packed into K_n without overlapping edges. Gerbner, Keszegh and Palmer [1] proposed a stronger conjecture: any sequence T_1,T_2,...,T_{n-1} can be packed into an arbitrary n-chromatic graph.

As a first step, they [2] asked whether any sequence T_1,T_2,...,T_{n-1} of paths and stars can be packed into any n-chromatic graph G. For G=K_n this is proved independently in [3] (with a five-page proof) and in [4] (with a "`proof without words''). I will show that both proofs extend easily for any n-chromatic graph G (see [5]).

[1] D. Gerbner, B. Keszegh, C. Palmer, Generalizations of the tree packing conjecture, Discussiones Mathematicae, Graph Theory, 32 (2012) 569--582. [2] D. Gerbner, B. Keszegh, C. Palmer, Red-blue alternating paths, Third Emléktábla Workshop, 2011, p.25 {} [3] A. Gyarfas, J. Lehel, Packing trees of different order into K_n, Combinatorics, Proc. Fifth Hungarian Coll. Keszthely, 1976, Vol II. North Holland. Colloq. Math. Soc. J. Bolyai 18 , 463--469. [4] S. Zaks, C. L. Liu, Decomposition of graphs into trees, Proceedings of 8-th Southeastern Conference on Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, La. Utilitas Math., Congressus Numerantium (1977), 643--654. [5] A. Gyarfas, Packing trees into n-chromatic graphs, Discussiones Mathematicae, Graph Theory, 34 (2014) 199--201.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to