Isomorphic Factorization of Trees of Maximum Degree Three

P. Horak1, X. Zhu2
1Department of Mathematics and Statistics, Simon Fraser University, Canada; and Katedra Matematiky, EF STU, 812 19 Bratislava, Slovakia
2Departement of Mathematics and Statistics, Simon Fraser University, Canada

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.