Oriented chromatic number of grids is greater than 7

By a coloring graph we mean an oriented graph H without self loops and with no arcs going in opposite directions. We say that the coloring graph H colors   an oriented graph G=(VG,AG)G=(VG,AG) if there is a homomorphism from G to H. In this paper we show that there exist 2-dimensional oriented grids, that cannot be colored by any coloring graph on seven vertices. Our proof is computer-aided. We describe two algorithms. The first one lists all non-isomorphic coloring graphs on seven vertices. The second one, given a coloring graph H on seven vertices, builds an oriented grid G, that cannot be colored by H. Using these two algorithms, we have found eight oriented grids, such that there exists no coloring graph H on seven vertices which colors all eight of them. One can then build one big grid, which contains these eight grids as subgraphs, and which is not colorable by any graph on seven vertices. This disproves the conjecture raised by Fertin et al. in [Inform. Process. Lett. 85 (2003) 261–266].

► List of all non-isomorphic coloring graphs with seven vertices. ► We build oriented grids which cannot be colored by homomorphism to coloring graphs. ► Oriented chromatic number of grids is greater than 7.