On Cartesian products of signed graphs (Q5896107): Difference between revisions
From MaRDI portal
EloiFerrer (talk | contribs) Page on [mardi] deleted: Publication:5896107 |
EloiFerrer (talk | contribs) Merged Item from Q5918775 |
||||||||||||||
description / en | description / en | ||||||||||||||
scientific article; zbMATH DE number 7567779 | |||||||||||||||
Property / zbMATH Open document ID | |||||||||||||||
Property / zbMATH Open document ID: 1494.05051 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / DOI | |||||||||||||||
Property / DOI: 10.1016/j.dam.2021.03.023 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / published in | |||||||||||||||
Property / published in: Discrete Applied Mathematics / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / publication date | |||||||||||||||
4 August 2022
| |||||||||||||||
Property / publication date: 4 August 2022 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 05C15 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 68R10 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH DE Number | |||||||||||||||
Property / zbMATH DE Number: 7567779 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
signed graphs | |||||||||||||||
Property / zbMATH Keywords: signed graphs / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
Cartesian products | |||||||||||||||
Property / zbMATH Keywords: Cartesian products / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
prime factor decomposition | |||||||||||||||
Property / zbMATH Keywords: prime factor decomposition / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
chromatic number | |||||||||||||||
Property / zbMATH Keywords: chromatic number / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / OpenAlex ID | |||||||||||||||
Property / OpenAlex ID: W3159499939 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / review text | |||||||||||||||
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. | |||||||||||||||
Property / review text: 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. / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / reviewed by | |||||||||||||||
Property / reviewed by: V. Lokesha / rank | |||||||||||||||
Normal rank | |||||||||||||||
links / mardi / name | links / mardi / name | ||||||||||||||
Revision as of 14:41, 29 April 2024
scientific article; zbMATH DE number 7567779
Language | Label | Description | Also known as |
---|---|---|---|
English | On Cartesian products of signed graphs |
scientific article; zbMATH DE number 7567779 |
Statements
On Cartesian products of signed graphs (English)
0 references
21 July 2020
0 references
4 August 2022
0 references
prime factor decomposition of signed graphs
0 references
signed graphs
0 references
Cartesian products
0 references
prime factor decomposition
0 references
chromatic number
0 references
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.
0 references