Packing Trees in Planar Graphs



Let T_1 and T_2 be two trees of order n. It is known [M1] that if neither tree is a star, then there is a graph G of order n whose edges can be two-colored such that the edges of color i are isomorphic to T_i.  The following conjecture asserts that we can further require G to be planar.

Question: If T_1 and T_2 are trees of order n that are not stars, then there is a planar graph that can be two-edge-colored such that the edges of color i are isomorphic to T_i.

The conjecture is known to be true if T_1 is a path, or even a cycle. An algorithm for finding such an embedding was given by Meszka [M2].

References:

[GHHNT] A. Garcia, C. Hernando, F. Hurtado, M. Noy, and J. Tejel, Packing trees into planar graphs, J. Graph Theory 40 (2002) 172-181.

[M1] Packing of graphs and permutations a survey, Discrete Math., to appear

[M2] Packing two copies of a tree into planar graph, M. Meszka, manuscript


Send comments to dan.archdeacon@uvm.edu

November, 2003