zbMATH — the first resource for mathematics

Colouring of generalized signed triangle-free planar graphs. (English) Zbl 1403.05049
Summary: 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.

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
Full Text: DOI
[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.