Extending edge colorings of distance-3 matchings in the Cartesian product of graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910049803173888 |
|---|---|
| author | Bärnkopf, Pál Győri, Ervin |
| author_facet | Bärnkopf, Pál Győri, Ervin |
| contents | We investigate the problem of extending partial edge colorings in Cartesian products of graphs, with a particular focus on cases where the precolored edges form a matching. Casselgren, Granholm, and Petros conjectured that any precolored distance-3 matching in $G = C^d_{2k}$ can be extended to a $2d$-edge coloring. In this paper, we prove a theorem that implies this conjecture. Especially, our main result establishes that a precolored distance-3 matching in the Cartesian product of certain class 1 graphs can be extended to an edge coloring that uses at most as many colors as the chromatic index, provided that certain degree conditions are satisfied. In the second part of the paper, we extend these results to Cartesian products of other types of graphs as well. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_09973 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Extending edge colorings of distance-3 matchings in the Cartesian product of graphs Bärnkopf, Pál Győri, Ervin Combinatorics We investigate the problem of extending partial edge colorings in Cartesian products of graphs, with a particular focus on cases where the precolored edges form a matching. Casselgren, Granholm, and Petros conjectured that any precolored distance-3 matching in $G = C^d_{2k}$ can be extended to a $2d$-edge coloring. In this paper, we prove a theorem that implies this conjecture. Especially, our main result establishes that a precolored distance-3 matching in the Cartesian product of certain class 1 graphs can be extended to an edge coloring that uses at most as many colors as the chromatic index, provided that certain degree conditions are satisfied. In the second part of the paper, we extend these results to Cartesian products of other types of graphs as well. |
| title | Extending edge colorings of distance-3 matchings in the Cartesian product of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2310.09973 |