The odd independence number of graphs, II: Finite and infinite grids and chessboard graphs

Abstract

An odd independent set $S$ in a graph $G=(V,E)$ is an independent set of vertices such that, for every vertex $v\in V\setminus S$, either $N(v)\cap S=\varnothing$ or $|N(v)\cap S|\equiv 1$ (mod 2), where $N(v)$ stands for the open neighborhood of $v$. The largest cardinality of odd independent sets of a graph $G$, denoted ${\alpha }_{od}(G)$, is called the odd independence number of $G$. This new parameter is a natural companion to the recently introduced strong odd chromatic number. A proper vertex coloring of a graph $G$ is a strong odd coloring if, for every vertex $v\in V(G)$, each color used in the neighborhood of $v$ appears an odd number of times in $N(v)$. The minimum number of colors in a strong odd coloring of $G$ is denoted by ${\chi }_{so}(G)$. A simple relation involving these two parameters and the order $|G|$ of $G$ is ${\alpha }_{od}(G)\cdot {\chi }_{so}(G)\ge |G|$, parallel to the same on chromatic number and independence number. In the present work, which is a companion to our first paper on the subject [The odd independence number of graphs, I: Foundations and classical classes], we focus on grid-like and chessboard-like graphs and compute or estimate their odd independence number and their strong odd chromatic number. Among the many results obtained, the following give the flavour of this paper: (1) $0.375\le {\varrho }_{od}(P_{\infty }\square P_{\infty })\le \mathrm{0.384615...}$, where ${\varrho }_{od}(P_{\infty }\square P_{\infty })$ is the odd independence ratio. (2) ${\chi }_{so}(G_d)=3$ for all $d\ge 1$, where $G_d$ is the infinite $d$-dimensional grid. As a consequence, ${\varrho }_{od}(G_d)\ge 1/3$. (3) The $r$-King graph $G$ on $n^2$ vertices has ${\alpha }_{od}(G)=\lceil n/(2r+1){\rceil }^2$. Moreover, ${\chi }_{so}(G)=(2r+1{)}^2$ if $n\ge 2r+1$, and ${\chi }_{so}(G)=n^2$ if $n\le 2r$. Many open problems are given for future research.

42 pages