Avoiding and Extending Partial Edge Colorings of Hypercubes
Carl Johan Casselgren, Per Johansson, Klas Markström · Graphs and Combinatorics · 2022
Abstract We consider the problem of extending and avoiding partial edge colorings of hypercubes; that is, given a partial edge coloring $$\varphi $$ φ of the d-dimensional hypercube $$Q_d$$ Q d , we are interested in whether there is a proper d-edge coloring of $$Q_d$$ Q d that agrees with the coloring $$\varphi $$ φ on every edge that is colored under $$\varphi $$ φ ; or, similarly, if there is a proper d-edge coloring that disagrees with $$\varphi $$ φ on every edge that is colored under $$\varphi $$ φ . In particular, we prove that for any $$d\ge 1$$ d ≥ 1 , if $$\varphi $$ φ is a partial d-edge coloring of $$Q_d$$ Q d , then $$\varphi $$ φ is avoidable if every color appears on at most d/8 edges and the coloring satisfies a relatively mild structural condition, or $$\varphi $$ φ is proper and every color appears on at most $$d-2$$ d - 2 edges. We also show that $$\varphi $$ φ is avoidable if d is divisible by 3 and every color class of $$\varphi $$ φ is an induced matching. Moreover, for all $$1 \le k \le d$$ 1 ≤ k ≤ d , we characterize for which configurations consisting of a partial coloring $$\varphi $$ φ of $$d-k$$ d - k edges and a partial coloring $$\psi $$ ψ of k edges, there is an extension of $$\varphi $$ φ that avoids $$\psi $$ ψ .