Isomorphic Factorization of Trees of Maximum Degree Three

Abstract

We prove that for any tree $T$ of maximum degree three, there exists a subset $S$ of $E(T)$ with $|S|=O(\log n)$ and a two-coloring of the edges of the forest $T\setminus S$ such that the two monochromatic forests are isomorphic, where $n$ is the number of vertices of $T$ of degree three.