2-edge-colored chromatic number of grids is at most 9 (Q2175809): Difference between revisions

A 2-edge-colored graph is a pair \((G,\sigma)\), where \(G\) is an undirected graph and \(\sigma:E(G)\to \{-, +\}\) is a function assigning a sign to each of the edges. A 2-edge-colored coloring of a 2-edge-colored graph \((G,\sigma)\) is a proper coloring \(\phi\) of \(V(G)\) such that if there exist edges \(\{u,v\}\) and \(\{x,y\}\) with \(\phi(u)=\phi(x)\) and \(\phi(v)=\phi(y)\), then \(\{u,v\}\) and \(\{x,y\}\) have the same sign. The 2-edge-colored chromatic number of the 2-edge-colored graph \((G,\sigma)\) is the minimum number of colors required for a 2-edge-colored coloring. The 2-edge-colored chromatic number of a graph \(G\), denoted by \(\chi_2(G)\), is the maximum over all 2-edge-colored of \(G\). Given a graph class \(\mathcal{F}\), the 2-edge-colored chromatic number \(\chi_2(\mathcal{F})\) is the maximum of the 2-edge-colored chromatic numbers of the elements in \(\mathcal{F}\). This paper deals with the 2-edge-colored chromatic number for the class of 2-dimensional grids \(\mathcal{G}\), where a grid is the Cartesian product of two paths. The author shows that \(8\leq\chi_2(\mathcal{G})\leq 9\) and \(7\leq\chi_2(\mathcal{G}_3)\leq 8\) for the class \(\mathcal{G}_3\) of grids with 3 columns. These results improve the bounds in [\textit{J. Bensmail}, Aust. J. Combin. 75, No. 3, 365--384 (2019; Zbl 1429.05059)].