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.
- 4-colouring of generalized signed planar graphs
- A note on complex-4-colorability of signed planar graphs
- A note on not-4-list colorable planar graphs
- A refinement of choosability of graphs
- Circular chromatic number of signed graphs
- Concepts of signed graph coloring
- Homomorphisms of 2-edge-colored triangle-free planar graphs
- Homomorphisms of edge-colored graphs and Coxeter groups
- Homomorphisms of signed graphs
- Homomorphisms of signed graphs: an update
- Note on a paper of B. Grünbaum on acyclic colorings
- On acyclic colorings of planar graphs
- On the 4-color theorem for signed graphs
- Signed graph coloring
- The chromatic number of a signed graph
- Signed planar graphs with given circular chromatic numbers
- On the 4-color theorem for signed graphs
- The complexity of signed graph and edge-coloured graph homomorphisms
- Walk-powers and homomorphism bounds of planar signed graphs
- Homomorphisms of signed graphs
- Packing Signatures in Signed Graphs
- Density of 2-critical signed graphs
- A note on complex-4-colorability of signed planar graphs
This page was built for publication: Complex and homomorphic chromatic number of signed planar simple graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117521)
