The Vertex Deletion Number of $C_n \times C_m$

The vertex deletion number of a graph $G$ is the smallest integer $k \geq 0$ such that there is a planar induced subgraph of $G$ obtained by the removal of $k$ vertices from $G$. In this work we study the vertex deletion number of $C_n\times C_m$, the rectangular grid with toroidal topology. We prove the extact result $\min\{n,m\} - \xi_{5,9}(n,m)$, where $\xi_{i,j}(k_1,k_2)$ is the number of true conditions among the following: (i) $k_1 = k_2 \leq i$ and (ii) $k_1 + k_2 \leq j$.

1999