paper

Signified chromatic number of grids is at most 9

arXiv:1909.00371 · doi:10.1007/s00373-020-02155-y

Abstract

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

References in corpus (1)

Cited by in corpus (1)