Signified chromatic number of grids is at most 9

Abstract

A signified graph is a pair $(G,\Sigma )$ where $G$ is a graph, and $\Sigma$ is a set of edges marked with '$-$'. Other edges are marked with '$+$'. A signified coloring of the signified graph $(G,\Sigma )$ is a homomorphism into a signified graph $(H,\Delta )$. The signified chromatic number of the signified graph $(G,\Sigma )$ is the minimum order of $H$. In this paper we show that for every 2-dimensional grid $(G,\Sigma )$ there exists homomorphism from $(G,\Sigma )$ into the signed Paley graphs $S{P}_9$. Hence signified chromatic number of the signified grids is at most 9. This improves upper bound on this number obtained recently by Bensmail.

Cited by in corpus (1)

• A Note on Colourings of Connected $2$-edge Coloured Cubic Graphs