Complex and homomorphic chromatic number of signed planar simple graphs
type: Item
instance of: scholarly article
title: Complex and homomorphic chromatic number of signed planar simple graphs
zbMATH Open document ID: 1498.05103
author: Reza Naserasr
author: Lan Anh Pham
published in: Graphs and Combinatorics
publication date: 2022-03-21T00:00:00Z
review text: Let \((G,\sigma)\) be a signed graph where \(G=(V,E)\) is a graph and \(\sigma:E\to \{+,-\}\) is a mapping giving a sign to each edge of \(G\). This paper deals with a notion of coloring of signed graphs that is an extension of the one presented in [\textit{T. Zaslavsky}, Discrete Math. 39, No. 2, 215--228 (1982; Zbl 0487.05027)]. Let \(\mathbb{C}_{k,l} = \{\pm 1, \pm 2,\ldots,\pm k\} \cup \{\pm 1i, \pm 2i,\ldots,\pm li\}\) where \(i = \sqrt{-1}\). A signed graph \((G,\sigma)\) is \((k,l)\)-colorable if there exists a mapping \(c:V\to \mathbb{C}_{k,l}\) such that \(c(x)c(y)\neq\sigma(xy)|c(x)^2|\) for every edge \(xy\) of \(G\). The complex chromatic number of a signed graph \((G,\sigma)\), written \(\chi_{\mathrm{com}}(G,\sigma)\), is the smallest order of \(\mathbb{C}_{k,l}\) such that \((G,\sigma)\) is \((k,l)\)-colorable. The authors disprove that every signed planar simple graph is \((2,0)\)-colorable. This problem was conjectured in [\textit{E. Máčajová} et al., Electron. J. Comb. 23, No. 1, Research Paper P1.14, 10 p. (2016; Zbl 1329.05116)] and recently disproved in [\textit{F. Kardoš} and \textit{J. Narboni}, Eur. J. Comb. 91, Article ID 103215, 8 p. (2021; Zbl 1458.05073)]. The authors also disprove that every signed planar simple graph is \((1,1)\)-colorable, which was conjectured in [\textit{Y. Jiang} and \textit{X. Zhu}, Electron. J. Comb. 27, No. 3, Research Paper P3.31, 23 p. (2020; Zbl 1446.05032)]. Using those results, they demonstrate the existence of a signed planar simple graph \((G,\sigma)\) with \(\chi_{\mathrm{com}}(G,\sigma)>4\). Lastly, the authors investigate relationships between \(\chi_{\mathrm{com}}(G,\sigma)\) and notions related to homomorphisms of signed graphs.
reviewed by: Margherita Maria Ferrari
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 7493899
zbMATH Keywords: coloring
zbMATH Keywords: signed graphs
zbMATH Keywords: planar graphs
MaRDI profile type: Publication
full work available at URL: s00373-021-02433-3
OpenAlex ID: W3103437050
Wikidata QID: Q123142740
cites work: Homomorphisms of edge-colored graphs and Coxeter groups
cites work: On acyclic colorings of planar graphs
cites work: \(4\)-colouring of generalized signed planar graphs
cites work: On the 4-color theorem for signed graphs
cites work: A note on complex-4-colorability of signed planar graphs
cites work: A note on not-4-list colorable planar graphs
cites work: The chromatic number of a signed graph
cites work: Homomorphisms of Signed Graphs
cites work: Homomorphisms of signed graphs: an update
cites work: Circular chromatic number of signed graphs
cites work: Homomorphisms of 2‐Edge‐Colored Triangle‐Free Planar Graphs
cites work: Concepts of signed graph coloring
cites work: Note on a paper of B. Grünbaum on acyclic colorings
cites work: Signed graph coloring
cites work: A refinement of choosability of graphs
DOI: 10.1007/S00373-021-02433-3
description: scientific article; zbMATH DE number 7493899