Colouring of generalized signed triangle-free planar graphs.

*(English)*Zbl 1403.05049Summary: We view an undirected graph \(G\) as a symmetric digraph, where each edge \(x y\) is replaced by two opposite arcs \(e = (x, y)\) and \(e^{- 1} = (y, x)\). Assume \(S\) is an inverse closed subset of permutations of positive integers. We say \(G\) is \(S\)-\(k\)-colourable if for any mapping \(\sigma : E(G) \rightarrow S\) with \(\sigma(x, y) = (\sigma(y, x))^{- 1}\), there is a mapping \(f : V(G) \rightarrow [k] = \{1, 2, \dots, k \}\) such that \(\sigma_e(f(x)) \neq f(y)\) for each arc \(e = (x, y)\). The concept of \(S\)-\(k\)-colourable is a common generalization of several other colouring concepts. This paper is focused on finding the sets \(S\) such that every triangle-free planar graph is \(S\)-3-colourable. Such a set \(S\) is called TFP-good. Grötzsch’s theorem is equivalent to say that \(S = \{\mathrm{id} \}\) is TFP-good. We prove that for any inverse closed subset \(S\) of \(S_3\) which is not isomorphic to \(\{\mathrm{id},(12) \}\), \(S\) is TFP-good if and only if either \(S = \{\mathrm{id} \}\) or there exists \(a \in [3]\) such that for each \(\pi \in S\), \(\pi(a) \neq a\). It remains an open question to determine whether or not \(S = \{\mathrm{id},(12) \}\) is TFP-good.

##### MSC:

05C15 | Coloring of graphs and hypergraphs |

05C10 | Planar graphs; geometric and topological aspects of graph theory |

05C22 | Signed and weighted graphs |

05C20 | Directed graphs (digraphs), tournaments |

##### Keywords:

triangle-free planar graphs; List colouring; oriented graphs; signed graphs; \(S\)-colouring
PDF
BibTeX
XML
Cite

\textit{Y. Jiang} et al., Discrete Math. 342, No. 3, 836--843 (2019; Zbl 1403.05049)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Z. Dvořák, L. Postle, List-coloring embedded graphs without cycles of lengths \(4\) to \(8\), 2015, preprint. https://arxiv.org/abs/150803437. |

[2] | Grötzsch, H., Ein dreifarbensatz für dreikreisfreie netze auf der kugel, Math.-Natur. Reihe, 8, 109-120, (1959) |

[3] | Jaeger, F.; Linial, N.; Payan, C.; Tarsi, M., Group connectivity of graphs— a non-homongenous analogue of nowhere-zero flow, J. Combin. Theory Ser. B, 56, 165-182, (1992) · Zbl 0824.05043 |

[4] | L. Jin, T. Wong, X. Zhu, Colouring of generlized signed planar graphs, manuscript, 2017. |

[5] | Kang, Y.; Steffen, E., Circular coloring of signed graphs, J. Graph Theory, 1-4, (2017) |

[6] | Máčajová, E.; Raspaud, A.; Škoviera, M., The chromatic number of a signed graph, Electron. J. Combin., 23, 1, (2016), #P114 · Zbl 1329.05116 |

[7] | Montassier, M., A note on the not \(3\)-choosability of some families of planar graphs, Inform. Process. Lett., 99, 68-71, (2006) · Zbl 1184.05048 |

[8] | Voigt, M., A not \(3\)-choosable planar graph without \(3\)-cycles, Discrete Mathmatics, 146, 325-328, (1995) · Zbl 0843.05034 |

[9] | Zaslavsky, T., Signed graph coloring, Discrete Math., 39, 215-228, (1982) · Zbl 0487.05027 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.