Extending edge-colorings of distance-2 matchings in the hypercube
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910035047612416 |
|---|---|
| author | Bärnkopf, Pál |
| author_facet | Bärnkopf, Pál |
| contents | 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 \mathbin{\Box} K_{2m}$ 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} K_{1,m}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_15764 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Extending edge-colorings of distance-2 matchings in the hypercube Bärnkopf, Pál Combinatorics 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 \mathbin{\Box} K_{2m}$ 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} K_{1,m}$. |
| title | Extending edge-colorings of distance-2 matchings in the hypercube |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.15764 |