Seminar

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 {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.
Organizers
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU

Program
Contact

Klas Markström

klas.markstrom@math.umu.se

Other
information

For practical matters at the Institute, send an e-mail to secretary@mittag-leffler.se