Complex and homomorphic chromatic number of signed planar simple graphs
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.
scientific article; zbMATH DE number 7493899
scientific article