Edge coloring of products of signed graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913390993080320 |
|---|---|
| author | Janczewski, Robert Turowski, Krzysztof Wróblewski, Bartłomiej |
| author_facet | Janczewski, Robert Turowski, Krzysztof Wróblewski, Bartłomiej |
| contents | In 2020, Behr defined the problem of edge coloring of signed graphs and showed that every signed graph $(G, σ)$ can be colored using exactly $Δ(G)$ or $Δ(G) + 1$ colors, where $Δ(G)$ is the maximum degree in graph $G$.
In this paper, we focus on products of signed graphs. We recall the definitions of the Cartesian, tensor, strong, and corona products of signed graphs and prove results for them. In particular, we show that $(1)$ the Cartesian product of $Δ$-edge-colorable signed graphs is $Δ$-edge-colorable, $(2)$ the tensor product of a $Δ$-edge-colorable signed graph and a signed tree requires only $Δ$ colors and $(3)$ the corona product of almost any two signed graphs is $Δ$-edge-colorable. We also prove some results related to the coloring of products of signed paths and cycles. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_02691 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Edge coloring of products of signed graphs Janczewski, Robert Turowski, Krzysztof Wróblewski, Bartłomiej Combinatorics Discrete Mathematics Data Structures and Algorithms 05C15 In 2020, Behr defined the problem of edge coloring of signed graphs and showed that every signed graph $(G, σ)$ can be colored using exactly $Δ(G)$ or $Δ(G) + 1$ colors, where $Δ(G)$ is the maximum degree in graph $G$. In this paper, we focus on products of signed graphs. We recall the definitions of the Cartesian, tensor, strong, and corona products of signed graphs and prove results for them. In particular, we show that $(1)$ the Cartesian product of $Δ$-edge-colorable signed graphs is $Δ$-edge-colorable, $(2)$ the tensor product of a $Δ$-edge-colorable signed graph and a signed tree requires only $Δ$ colors and $(3)$ the corona product of almost any two signed graphs is $Δ$-edge-colorable. We also prove some results related to the coloring of products of signed paths and cycles. |
| title | Edge coloring of products of signed graphs |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms 05C15 |
| url | https://arxiv.org/abs/2312.02691 |