A note on complex-4-colorability of signed planar graphs

DOI10.37236/9844MaRDI QIDQ831346zbMATH OpenOpenAlexFDO

Authors Arnfried Kemnitz, Margit Voigt

Publication date 11 May 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.37236/9844

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chromatic number of a signed graphnon-4-colourable signed planar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Review text

A pair \((G, \sigma )\) is called a signed graph if \(\sigma: E(G) \to\{1,-1\}\) is a mapping which assigns to each edge \(e\) of \(G\) a sign \(\sigma(e)\in\{1,-1\}\). \textit{T. Zaslavsky} [Discrete Math. 39, 215--228 (1982; Zbl 0487.05027)] introduced coloring of signed graph, after many works are undertaken by researchers and various papers published. If \((G,\sigma)\) is a signed graph, then a complex-4-coloring of \((G,\sigma)\) is a mapping \( f:V(G)\to\{1,-1,i,-i\}\) with \(i =\sqrt{-1}\) such that \(f(u)f(v) \not=\sigma(e)\) for every edge \(e=uv\) of \(G\). Here, the authors prove that there are signed planar graphs that are not complex-4-colorable. This result completes investigations of \textit{L. Jin} et al. [Eur. J. Comb. 92, Article ID 103198, 6 p. (2021; Zbl 1458.05072)] as well as \textit{Y. Jiang} and \textit{X. Zhu} [Electron. J. Comb. 27, No. 3, P3.31, 23 p. (2020; Zbl 1446.05032)] on 4-colorings of generalized signed planar graphs disproving a conjecture of \textit{L. Jin} et al. [``Colouring of generalized signed planar graphs, Preprint, \url{arXiv:1811.08584}]. This paper contains a useful information to researchers working in the areas of coloring and signed graph topics.

Recommendations

• 4-colouring of generalized signed planar graphs
• On the 4-color theorem for signed graphs
• Complex and homomorphic chromatic number of signed planar simple graphs
• Vertex signatures and edge-4-colorings of 4-regular plane graphs
• Circular \({\boldsymbol{(4-\epsilon )}}\) -Coloring of Some Classes of Signed Graphs
• A characterization of signed planar graphs with rank at most 4
• Colouring of generalized signed triangle-free planar graphs
• A note on not-4-list colorable planar graphs
• A note on total colorings of planar graphs without 4-cycles
• A sufficient condition for planar graphs to be DP-4-colorable

Cites work

• 4-colouring of generalized signed planar graphs
• Colouring of \(S\)-labelled planar graphs
• Signed graph coloring

Cited in

(6)

• Density of \(C_{-4}\)-critical signed graphs
• Complex and homomorphic chromatic number of signed planar simple graphs
• 4-colouring of generalized signed planar graphs
• On the 4-color theorem for signed graphs
• Colouring of \(S\)-labelled planar graphs
• Vertex signatures and edge-4-colorings of 4-regular plane graphs

This page was built for publication: A note on complex-4-colorability of signed planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q831346)