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].
[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 email@example.com