On the chromatic numbers of signed triangular and hexagonal grids (Q2234782)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the chromatic numbers of signed triangular and hexagonal grids |
scientific article |
Statements
On the chromatic numbers of signed triangular and hexagonal grids (English)
0 references
19 October 2021
0 references
A signed graph \(G\) consists of a graph \(G = (V,E)\) together with a signature (considered as an edge 2-coloring) \(s: E(G) \to \{1, -1\}\). A homomorphism from a signed graph \(G\) to a signed graph \(H\) is a mapping \(\phi: V(G) \to V(H)\) such that, after performing switching operations at a subset of vertices in \(V(G)\), every edge of \(G\) is mapped to an edge of \(H\) with the same sign. The chromatic number \(\chi_s(G)\) of a signed graph \(G\), is the order of a smallest signed graph \(H\) such that there exists a homomorphism from \(G\) to \(H\). It is shown that the chromatic number of a signed hexagonal grid is 4 and the chromatic number of a signed triangular grid is at most 10. At the end of the paper, an interesting conjectured is posed that the chromatic number of a signed triangular grid equals 6.
0 references
combinatorial problems
0 references
homomorphisms
0 references
chromatic number
0 references
signed graphs
0 references