Javascript must be enabled to continue!

The chromatic number of the Cartesian product of signed graphs

In [Formula: see text], Vizing showed that the chromatic number of the Cartesian product of two graphs is equal to the larger one of the chromatic numbers of these two graphs. This result shows that the chromatic number of the Cartesian product of graphs is determined by its factors’ chromatic numbers. In this paper, we study the chromatic number of the Cartesian product of signed graphs. For signed graphs, we find that the chromatic number of the Cartesian product is also determined by its factors. For any two signed graphs [Formula: see text] and [Formula: see text], we have [Formula: see text]. Moreover, if [Formula: see text] is even, then [Formula: see text]. For the case [Formula: see text] is odd, there are graphs that satisfy [Formula: see text] and [Formula: see text] respectively.

World Scientific Pub Co Pte Ltd

Liang Zhou Chao Wen Qiang Sun Chao Zhang

Discrete Mathematics, Algorithms and Applications

2026

Title: The chromatic number of the Cartesian product of signed graphs

Description:

In [Formula: see text], Vizing showed that the chromatic number of the Cartesian product of two graphs is equal to the larger one of the chromatic numbers of these two graphs.

This result shows that the chromatic number of the Cartesian product of graphs is determined by its factors’ chromatic numbers.

In this paper, we study the chromatic number of the Cartesian product of signed graphs.

For signed graphs, we find that the chromatic number of the Cartesian product is also determined by its factors.

For any two signed graphs [Formula: see text] and [Formula: see text], we have [Formula: see text].

Moreover, if [Formula: see text] is even, then [Formula: see text].

For the case [Formula: see text] is odd, there are graphs that satisfy [Formula: see text] and [Formula: see text] respectively.

Back

New setting is introduced to study neutrosophic failed-independent number and failed independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key t...

Independent Set in Neutrosophic Graphs

New setting is introduced to study neutrosophic independent number and independent neutrosophic-number arising neighborhood of different vertices. Neighbor is a key term to have th...

ON INCIDENCE COLORING OF SIGNED GRAPHS

An incidence of a graph $G$ is a pair $(x,e)$, where $x$ is a vertex of $G$ and $e$ is an edge of $G$ incident to $x$. Two incidences $(x,e)$ and $(y,f)$ are adjacent if any one of...

Planar graphs have bounded nonrepetitive chromatic number

The following seemingly simple question with surprisingly many connections to various problems in computer science and mathematics can be traced back to the beginning of the 20th c...

Effect of chromatic aberration on performance of concentrated multi-junction solar cells and their optimization

In order to investigate the influence of the chromatic aberration on the performance of multi-junction solar cells, the performance of the triple-junction GaInP/GaInAs/Ge solar cel...

Computing a Minimum Subset Feedback Vertex Set on Chordal Graphs Parameterized by Leafage

Abstract Chordal graphs are characterized as the intersection graphs of subtrees in a tree and such a representation is known as the tree model. Restricting the characteriz...

Chromatic Polynomial of Intuitionistic Fuzzy Graphs(IFGs) Using α-Levels

Abstract Objective: In graph coloring, determining the chromatic polynomial is exactly finding the number of alternative solutions anywhere graph coloring is applied. In th...

Cartesian magicness of 3-dimensional boards

A $(p, q, r)$-board that has $p q+p r+q r$ squares consists of a $(p, q)-$, a $(p, r)-$, and a $(q, r)$-rectangle. Let $S$ be the set of the squares. Consider a bijection $f: S \ri...

Email:
Password:

Email:

The chromatic number of the Cartesian product of signed graphs

Related Results