**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