# On the pushable chromatic number of various types of grids

1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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 $\overrightarrow{G}$ is the order of a smallest (in terms of vertices) oriented graph $\overrightarrow{H}$ such that, by pushing vertices in $\overrightarrow{G}$, we can obtain an oriented graph $\overrightarrow{G}'$ that admits an oriented $\overrightarrow{H}$-colouring, \textit{i.e.}, a vertex-mapping $\phi:V(\overrightarrow{G}') \rightarrow V(\overrightarrow{H})$ preserving the arcs (for every arc $\overrightarrow{uv}$ of $\overrightarrow{G}'$, the arc $\overrightarrow{\phi(u)\phi(v)}$ exists in $\overrightarrow{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.
Keywords :
Document type :
Reports

https://hal.archives-ouvertes.fr/hal-03531789
Contributor : Julien Bensmail Connect in order to contact the contributor
Submitted on : Tuesday, January 18, 2022 - 12:22:24 PM
Last modification on : Friday, January 21, 2022 - 3:20:13 AM

### File

push-grids.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-03531789, version 1

### Citation

Julien Bensmail, Tapas Das, Dimitri Lajou, Soumen Nandi, Sagnik Sen. On the pushable chromatic number of various types of grids. [Research Report] Université Côte d'Azur; Université de Bordeaux. 2022. ⟨hal-03531789⟩

Record views