Edge precoloring extension of trees II
Carl Johan Casselgren, Fikre Bogale Petros · Discussiones Mathematicae Graph Theory · 2022
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 ψ.