On Cartesian products of signed graphs (Q5896107): Difference between revisions

The Cartesian product of signed graphs is defined by \textit{K. A. Germina} et al. [Linear Algebra Appl. 435, No. 10, 2432--2450 (2011; Zbl 1222.05223)]. Here, the authors focus on its algebraic properties and look at the chromatic number of some Cartesian products. The main result is the unicity of the prime factor decomposition of signed graphs. This leads the author to present an algorithm to compute this decomposition in linear time based on a decomposition algorithm for oriented graphs by \textit{W. Imrich} and \textit{I. Peterin} [Discrete Math. 341, No. 5, 1336--1343 (2018; Zbl 1383.05271)]. The chromatic number of a signed graph, that is the minimum order of a signed graph to which the input signed graph admits a homomorphism, of graphs with an underlying graph of the form \(P_n\square P_m\), of Cartesian products of signed paths, of Cartesian products of signed complete graphs and of Cartesian products of signed cycles are studied. \textit{T. Zaslavsky} [Discrete Appl. Math. 4, 47--74 (1982; Zbl 0476.05080)] gave a way to determine if two signed graphs are equivalent in linear time. Note that there is a difference between considering the chromatic number of the Cartesian product of two signed graphs and the chromatic number of a signed graph whose underlying graph is a Cartesian product. This is an interesting and nicely explained paper and useful to signed graph researchers.