On the pushable chromatic number of various types of grids

Pushing a vertex in an oriented graph means reversing the direction of all the arcs incident to that vertex, resulting in another oriented graph. The pushable chromatic number of an oriented graph #>> Gis the order of a smallest (in terms of vertices) oriented graph H #>> such that, bypushing vertices in G#>>, we can obtain an oriented graph G#>>' that admits an oriented H#>>-colouring, i.e., a vertex-mapping phi : V(G#>>') -> V(H#>>) preserving the arcs (for every arc # >> uv of #>> G ', the arc # >> phi(u)phi(v)exists in H#>>). This notion extends to (undirected) graphs and families of graphs: the pushable chromatic number of a graph is the maximum pushable chromatic number over all its orientations, while the pushable chromatic number of a family of graphs is the maximum pushable chromatic number over all its members.We here initiate the study of the pushable chromatic number of several types of grids. For hexagonal grids, we determine that the pushable chromatic number is exactly 4. For square grids, we show that the pushable chromatic number is 5 or 6. For triangular grids, we prove that the pushable chromatic number lies in between 7 and 12. The pushable chromatic number of graphs is, together with the oriented chromatic number, the 2-edge-coloured chromatic number, and the signed chromatic number, part of a group of four chromatic parameters that tend to behave in a very comparable way in general. Following the current work, all of these four parameters have now been investigated in the context of several grids. We take this occasion to summarise the current knowledge on the behaviour of these four chromatic parameters in these graphs.(c) 2023 Elsevier B.V. All rights reserved.