Extending edge-colorings of distance-2 matchings in the hypercube

Abstract

Casselgren, Markstörm, and Pham conjectured that any precolored dis\-tan\-ce-2 matching in the $d$-dimensional cube $Q_d$ with at most $d$ colors can be extended to a proper $d$-edge-coloring. In this paper, we prove this conjecture and some related theorems. Especially, our result establishes that if $G$ is a bipartite graph, then a precolored distance-2 matching in the Cartesian product $H=G\square K_{2m}$ with at most ${\chi }^{\prime }(H)=\Delta (H)=\Delta (G)+2m-1$ colors can be extended to an edge-coloring using at most ${\chi }^{\prime }(H)$ colors. As another generalization, we establish a similar result for the Cartesian product $G\square K_{1,m}$.