2-Edge-Colored Chromatic Number of Grids is at Most 9

A 2-edge-colored graph is a pair (G,σ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(G, \sigma )$$\end{document} where G is a graph, and σ:E(G)→{'+','-'}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sigma :E(G)\rightarrow \{\text {'}+\text {'},\text {'}-\text {'}\}$$\end{document} is a function which marks all edges with signs. A 2-edge-colored coloring of the 2-edge-colored graph (G,σ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(G, \sigma )$$\end{document} is a homomorphism into a 2-edge-colored graph (H,δ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(H, \delta )$$\end{document}. The 2-edge-colored chromatic number of the 2-edge-colored graph (G,σ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(G, \sigma )$$\end{document} is the minimum order of H. In this paper we show that for every 2-dimensional grid (G,σ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(G, \sigma )$$\end{document} there exists a homomorphism from (G,σ)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(G, \sigma )$$\end{document} into the 2-edge-colored Paley graph SP9\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$SP_9$$\end{document}. Hence, the 2-edge-colored chromatic number of the 2-edge-colored grids is at most 9. This improves the upper bound on this number obtained recently by Bensmail. Additionally, we show that 2-edge-colored chromatic number of the 2-edge-colored grids with 3 columns is at most 8.