Partitioning infinite trees

A graph G is bisectable if its edges can be colored by two colors so that t he resulting monochromatic subgraphs are isomorphic. We show that any infin ite tree of maximum degree Delta with infinitely many vertices of degree at least Delta - 1 is bisectable as is any infinite tree of maximum degree De lta less than or equal to 14. Further, it is proved that every infinite tre e T of finite maximum degree contains a finite subset E of its edges so tha t the graph T-E is bisectable. To measure how "far" a graph G is from being bisectable, we define c(G) to be the smallest number k>1 so that there is a coloring of the edges of G by k colors with the property that any two mon ochromatic subgraphs are isomorphic. An upper bound on c(G), which is in a sense best possible, is presented. (C) 2000 John Wiley & Sons, Inc.