Edge Precoloring Extension of Trees

Sammanfattning: Given a set of k colors and a graph G with a subset S of precolored edges (a partial k-edge coloring of G), we consider the problem of determining whether G has a proper edge coloring of G with the same k colors (an extension of the partial coloring) where the colors of edges in S are not changed. If such a coloring exists, then the partial k-coloring is called extendable.Some scheduling problems as well as some combinatorial problems can be reformulated as partial edge coloring extension problems for corresponding graphs. Partial edge coloring extension problems seem to have been first considered in connection with the problem of completing partial Latin squares. In 1960 Evans stated his conjecture that any partial Latin square of size n with at most n – 1 non-empty cells can be completed to a Latin square of size n. In terms of edge colorings this is equivalent to the statement that any proper partial n-edge coloring of the balanced complete bipartite graph Kn,n with at most n – 1 precolored edges is extendable. This classical conjecture was proved by Smetaniuk (1981), and also independently by Andersen and Hilton (1983). Moreover, Andersen and Hilton completely characterized which partial Latin squares of size n with n non-empty cells that cannot be completed to a Latin square of size n. In addition, Andersen (1985) characterized partial Latin squares of size n with n+1 non-empty cells that are completable to Latin squares of size n.More recently, the problem of extending a partial edge coloring where the precolored edges form a matching has been considered by Edwards et al. (2018). Casselgren, Markstrom and Pham (2020) studied questions on extending partial edge colorings of the n-dimensional hypercubes Qn. In particular, they obtained an analogue of the positive solution to Evans' conjecture on completing partial Latin squares by proving that every proper partial edge coloring of at most n – 1 edges of Qn can be extended to a proper n-edge coloring of Qn. They also characterized which partial edge colorings of Qn with precisely n precolored edges are extendable to proper n-edge colorings of Qn.In this thesis we study similar partial edge coloring extension problems for trees. Let T be a tree with maximum degree Δ(T). First, we characterize which partial edge colorings with at most Δ(T) precolored edges in T that are extendable to proper Δ(T)-edge colorings, thereby proving an analogue of the aforementioned result by Andersen and Hilton for Latin squares. Then, we prove an analogue for trees of the result of Andersen by characterizing exactly which precolorings of at most Δ(T) + 1 precolored edges in a tree T that are extendable to Δ(T)-edge colorings of T. We also prove sharp conditions on when it is possible to extend a precolored matching or a collection of connected precolored subgraphs of a tree T to a Δ(T)-edge coloring of T. Finally, we consider the problem of avoiding a given (not necessarily proper) partial edge coloring.