4-colouring of generalized signed planar graphs

DOI10.37236/9338MaRDI QIDQ2194082zbMATH OpenOpenAlexFDO

Authors Yiting Jiang, Xuding Zhu

Publication date 25 August 2020

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://arxiv.org/abs/1811.08584

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)

Abstract: Assume $G$ is a graph. We view $G$ as a symmetric digraph, in which each edge $uv$ of $G$ is replaced by a pair of opposite arcs $e=(u,v)$ and $e^{-1}=(v,u)$. 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)oS$ with $sigma(x,y)=(sigma(y,x){)}^{-1}$, there is a mapping $f:V(G)o[k]=1,2,ldots,k$ such that for each arc $e=(x,y)$, $sigm{a}_e(f(x))ef(y)$. The concept of $S$-$k$-colouring is a common generalization of many colouring concepts, including $k$-colouring, signed $k$-colouring defined by M'{a}v{c}ajov'{a}, Raspaud and v{S}koviera, signed $k$-colouring defined by Kang and Steffen, correspondence $k$-colouring defined by Dvov{r}'{a}k and Postle, and group colouring defined by Jaeger, Linial, Payan and Tarsi. We are interested in the problem as for which subset $S$ of $S_4$, every planar graph is $S$-colourable. Such a subset $S$ is called good. The famous four colour theorem is equivalent to say that $S=id$ is good. There are two conjectures on signed graph colouring, one is equivalent to $S=id,(12)(34)$ be good and the other is equivalent to $S=id,(12)$ be good. We say two subsets $S$ and $S^{\prime }$ of $S_k$ are conjugate if there is a permutation $piin{S}_k$ such that $S^{\prime }=pisigmap{i}^{-1}:sigmainS$. This paper proves that if $S$ is a good subset of $S_4$ containing $id$, then $S$ is conjugate to a subset of $id,(12),(34),(12)(34)$. However, it remains an open problem if there is any good subset $S$ which contains $id$ and has cardinality $|S|ge2$. We also prove that $S=(12),(13),(23),(123),(132)$ is not good.

Recommendations

• Colouring of \(S\)-labelled planar graphs
• A note on complex-4-colorability of signed planar graphs
• Colouring of generalized signed triangle-free planar graphs
• Choosability in signed planar graphs
• On the 4-color theorem for signed graphs

Cites work

• scientific article; zbMATH DE number 890665 (Why is no real title available?)
• A note on group colorings
• A small non-\(\mathbb Z_4\)-colorable planar graph
• Biased graphs. III: Chromatic and dichromatic invariants
• Circular coloring of signed graphs
• Group connectivity and group colorings of graphs --- a survey
• Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties
• Signed graph coloring
• The chromatic number of a signed graph
• The chromatic spectrum of signed graphs

Cited in

(8)

• A note on complex-4-colorability of signed planar graphs
• Colouring of generalized signed triangle-free planar graphs
• Complex and homomorphic chromatic number of signed planar simple graphs
• Colouring of \(S\)-labelled planar graphs
• Generalized signed graphs of large girth and large chromatic number
• Vertex signatures and edge-4-colorings of 4-regular plane graphs
• Signed permutations and the four color theorem
• Separating signatures in signed planar graphs

This page was built for publication: \(4\)-colouring of generalized signed planar graphs

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