2025/09/19 by Pál Bärnkopf, Bärnkopf, Pál
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2509.15764
openalex publication_date 2025/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Casselgren, Markstörm, and Pham conjectured that any precolored dis\-tan\-ce-2 matching in the d-dimensional cube Qd 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 \mathbin\Box K2m with at most χ'(H) = Δ(H) = Δ(G) + 2m - 1 colors can be extended to an edge-coloring using at most χ'(H) colors. As another generalization, we establish a similar result for the Cartesian product G \mathbin\Box K1,m.