EDGE PRECOLORING EXTENSION OF TREES II.

We consider the problem of extending and avoiding partial edge colorings of trees; that is, given a partial edge coloring ϕ of a tree T we are interested in whether there is a proper Δ (T)-edge coloring of T that agrees with the coloring ϕ on every edge that is colored under ϕ; or, similarly, if there is a proper Δ (T)-edge coloring that disagrees with ϕ on every edge that is colored under '. We characterize which partial edge colorings with at most Δ (T) + 1 precolored edges in a tree T are extendable, thereby proving an analogue of a result by Andersen for Latin squares. Furthermore we obtain some\mixed" results on extending a partial edge coloring subject to the condition that the extension should avoid a given partial edge coloring; in particular, for all 0 ≤ k ≤ Δ (T), we characterize for which configurations consisting of a partial coloring ϕ of Δ (T)-k edges and a partial coloring ψ of k + 1 edges of a tree T, there is an extension of ϕ that avoids ψ. [ABSTRACT FROM AUTHOR]