Edge precoloring extension of trees II

Casselgren, Carl Johan  ; Petros, Fikre

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 613-637

Résumé

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 ψ.

Détail

Keywords: edge coloring, tree, precoloring extension, avoiding edge coloring