2-edge-colored chromatic number of grids is at most 9

Abstract: A signified graph is a pair

(G, S i g m a)

where

G

is a graph, and

S i g m a

is a set of edges marked with '

-

'. Other edges are marked with '

+

'. A signified coloring of the signified graph

(G, S i g m a)

is a homomorphism into a signified graph

(H, D e l t a)

. The signified chromatic number of the signified graph

(G, S i g m a)

is the minimum order of

H

. In this paper we show that for every 2-dimensional grid

(G, S i g m a)

there exists homomorphism from

(G, S i g m a)

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.

Recommendations

Cites Work

Cited In (4)

This page was built for publication: 2-edge-colored chromatic number of grids is at most 9