Article in volume
Authors:
Krzysztof Turowski
Theoretical Computer Science Department, Jagiellonian University
Title:
Edge coloring of products of signed graphs
PDFSource:
Discussiones Mathematicae Graph Theory 45(2) (2025) 763-786
Received: 2024-01-12 , Revised: 2024-06-21 , Accepted: 2024-06-21 , Available online: 2024-07-16 , https://doi.org/10.7151/dmgt.2553
Abstract:
In 2020, Behr defined the problem of edge coloring of signed graphs and
showed that every signed graph $(G, \sigma)$ can be colored using exactly
$\Delta(G)$ or $\Delta(G) + 1$ colors, where $\Delta(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 $\Delta$-edge-colorable signed graphs is
$\Delta$-edge-colorable, $(2)$ the tensor product of a $\Delta$-edge-colorable
signed graph and a signed tree requires only $\Delta$ colors and $(3)$ the
corona product of almost any two signed graphs is $\Delta$-edge-colorable.
We also prove some results related to the coloring of products of signed paths
and cycles.
Keywords:
signed graphs, edge coloring of signed graphs, graph products
References:
- R. Behr, Edge coloring signed graphs, Discrete Math. 343 (2020) 111654.
https://doi.org/10.1016/j.disc.2019.111654 - H. Cai, Q. Sun, G. Xu and S. Zheng, Edge Coloring of the signed generalized Petersen graph, Bull. Malays. Math. Sci. Soc. 45 (2022) 647–661.
https://doi.org/10.1007/s40840-021-01212-w - R. Diestel, Graph Theory, 5th Ed., Grad. Texts in Math. 173 (Springer Berlin, Heidelberg, 2017).
https://doi.org/10.1007/978-3-662-53622-3 - F. Harary, On the notion of balance of a signed graph, Michigan Math. J. 2 (1953/1954) 143–146.
https://doi.org/10.1307/mmj/1028989917 - F. Harary, On the coloring of signed graphs, Elem. Math. 23 (1968) 85–89.
https://doi.org/10.5169/seals-26032 - R. Janczewski, K. Turowski and B. Wróblewski, Edge coloring of graphs of signed class $1$ and $2$, Discrete Appl. Math. 338 (2023) 311–319.
https://doi.org/10.1016/j.dam.2023.06.029 - L. Jin, Y. Kang and E. Steffen, Choosability in signed planar graphs, European J. Combin. 52 (2016) 234–243.
https://doi.org/10.1016/j.ejc.2015.10.001 - Y. Kang, Hajós-like theorem for signed graphs, European J. Combin. 67 (2018) 199–207.
https://doi.org/10.1016/j.ejc.2017.08.003 - Y. Kang and E. Steffen, The chromatic spectrum of signed graphs, Discrete Math. 339 (2016) 2660–2663.
https://doi.org/10.1016/j.disc.2016.05.013 - Y. Kang and E. Steffen, Circular coloring of signed graphs, J. Graph Theory 87 (2018) 135–148.
https://doi.org/10.1002/jgt.22147 - F. Kardoš and J. Narboni, On the $4$-color theorem for signed graphs, European J. Combin. 91 (2021) 103215.
https://doi.org/10.1016/j.ejc.2020.103215 - E. Mácajová, A. Raspaud and M. Škoviera, The chromatic number of a signed graph, Electron. J. Combin. 23 (2016) #P1.14.
https://doi.org/10.37236/4938 - T. Schweser and M. Stiebitz, Degree choosable signed graphs, Discrete Math. 340 (2017) 882–891.
https://doi.org/10.1016/j.disc.2017.01.007 - E. Steffen and A. Vogel, Concepts of signed graph coloring, European J. Combin. 91 (2021) 103226.
https://doi.org/10.1016/j.ejc.2020.103226 - T. Zaslavsky, Signed graph coloring, Discrete Math. 39 (1982) 215–228.
https://doi.org/10.1016/0012-365X(82)90144-3 - T. Zaslavsky, How colorful the signed graph$?$, Discrete Math. 52 (1984) 279–284.
https://doi.org/10.1016/0012-365X(84)90088-8 - T. Zaslavsky, Balanced decompositions of a signed graph, J. Combin. Theory Ser. B 43 (1987) 1–13.
https://doi.org/10.1016/0095-8956(87)90026-8
Close