2-edge-colored chromatic number of grids is at most 9

Janusz Dybizbański


A 2-edge-colored graph is a pair (G,σ) where G is a graph, and σ:E(G)→{'+','−'} is a function which marks all edges with signs. A 2-edge-colored coloring of the 2-edge-colored graph (G,σ) is a homomorphism into a 2-edge-colored graph (H,δ). The 2-edge-colored chromatic number of the 2-edge-colored graph (G,σ) is the minimum order of H. In this paper we show that for every 2-dimensional grid (G,σ) there exists a homomorphism from (G,σ) into the 2-edge-colored Paley graph SP9. Hence, the 2-edge-colored chromatic number of the 2-edge-colored grids is at most 9. This improves the upper bound on this number obtained recently by Bensmail. Additionally, we show that 2-edge-colored chromatic number of the 2-edge-colored grids with 3 columns is at most 8.
Author Janusz Dybizbański (FMPI / II)
Janusz Dybizbański,,
- Institute of Informatics
Journal seriesGraphs and Combinatorics, ISSN 0911-0119, e-ISSN 1435-5914, (N/A 70 pkt)
Issue year2020
Publication size in sheets0.5
Keywords in English2-edge-colored coloring, grids, Paley graphs
ASJC Classification2607 Discrete Mathematics and Combinatorics; 2614 Theoretical Computer Science
URL https://doi.org/10.1007/s00373-020-02155-y
Languageen angielski
LicenseOther; published final; Uznanie Autorstwa (CC-BY); with publication
Score (nominal)70
Score sourcejournalList
ScoreMinisterial score = 70.0, 08-05-2020, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2018 = 0.854; WoS Impact Factor: 2018 = 0.488 (2) - 2018=0.563 (5)
Citation count*2 (2020-05-18)
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.
Are you sure?