Edge coloring of products of signed graphs

December 05, 2023 · The Ethereal · 🏛 Discussiones Mathematicae Graph Theory

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Robert Janczewski, Krzysztof Turowski, Bartłomiej Wróblewski arXiv ID 2312.02691 Category math.CO: Combinatorics Cross-listed cs.DM, cs.DS Citations 0 Venue Discussiones Mathematicae Graph Theory Last Checked 3 months ago
Abstract
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.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Combinatorics

🔮 🔮 The Ethereal

Tables of subspace codes

Daniel Heinlein, Michael Kiermaier, ... (+2 more)

math.CO 🏛 arXiv 📚 94 cites 10 years ago