Signed coloring of 2-dimensional grids

Janusz Dybizbański , Anna Nenca , Andrzej Szepietowski

Abstract

A signed graph is a pair(G,σ), where G=(V(G),E(G)) is an undirected graph and σ:E(G)→{+,−} is a function which marks each edge with “+” or “−”. Two signed graphs are equivalent if one of them can be changed to the other by a sequence of resigning operations. The single resigning operation chooses a vertex v∈V(G) and flips the signs of all edges incident to v. By[G,σ] we shall denote the equivalence class of the signed graph(G,σ). Each element of [G,σ] is called a presentation of [G,σ]. In this paper we shall call both (G,σ) and [G,σ] signed graphs. The coloring of signed graphs is defined through homomorphism. The signed graph [G,σ] is colored by the signed graph (G2,σ2), if there exists a presentation (G,σ1) of [G,σ] and a vertex-mapping φ from G to G2 which preserves signs of the edges. In this paper we show that:(a) The signed chromatic number for the class G of all 2-dimensional grids lies between 5 and 6. (b)Every signed grid with at most seven rows can be colored with five colors.(c)Every signed grid with two rows can be colored with four colors.
Author Janusz Dybizbański (FMPI / II)
Janusz Dybizbański,,
- Institute of Informatics
, Anna Nenca (FMPI / II)
Anna Nenca,,
- Institute of Informatics
, Andrzej Szepietowski (FMPI / II)
Andrzej Szepietowski,,
- Institute of Informatics
Journal seriesInformation Processing Letters, ISSN 0020-0190, e-ISSN 1872-6119, (N/A 70 pkt)
Issue year2020
Vol156
Pages1-6
Publication size in sheets0.5
Article number105918
Keywords in Englishgraphs, signed coloring, grids combinatorial problems
ASJC Classification1706 Computer Science Applications; 1710 Information Systems; 1711 Signal Processing; 2614 Theoretical Computer Science
DOIDOI:10.1016/j.ipl.2020.105918
URL https://doi.org/10.1016/j.ipl.2020.105918
Languageen angielski
LicenseOther; published final; Uznanie Autorstwa - Użycie Niekomercyjne - Bez utworów zależnych (CC-BY-NC-ND); with publication
Score (nominal)70
Score sourcejournalList
ScoreMinisterial score = 70.0, 27-02-2020, ArticleFromJournal
Publication indicators Scopus Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 0.972; WoS Impact Factor: 2018 = 0.914 (2) - 2018=0.843 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back
Confirmation
Are you sure?