Andras Gyarfas: Packing trees into n-chromatic graphs

ap>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 {http://www.renyi.hu/~emlektab/index/booklet.html}

[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.