4-colouring of generalized signed planar graphs

DOI10.37236/9338zbMATH Open1446.05032arXiv1811.08584OpenAlexW3083096111MaRDI QIDQ2194082FDOQ2194082

Authors: Yiting Jiang, Xuding Zhu 

Publication date: 25 August 2020

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

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.

Full work available at URL: https://arxiv.org/abs/1811.08584

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

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)

Cites Work

• Signed graph coloring
• Biased graphs. III: Chromatic and dichromatic invariants
• The chromatic number of a signed graph
• Group connectivity of graphs --- a nonhomogeneous analogue of nowhere-zero flow properties
• Group connectivity and group colorings of graphs --- a survey
• Title not available (Why is that?)
• A note on group colorings
• The chromatic spectrum of signed graphs
• A small non-\(\mathbb Z_4\)-colorable planar graph
• Circular coloring 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)