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

An odd independent set S in a graph $G=(V,E)$ is an independent set of vertices such that, for every vertex v ∈ V S, either N(v) ∩ S = ∅ or |N(v) ∩ S| ≡ 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 α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 ∈ 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 χₛₒ(G). A simple relation involving these two parameters and the order $|G|$ of G is αod(G)·χₛₒ(G) ≥ |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 ≤ od(P_∞ P_∞) ≤ 0.384615..., where od(P_∞ P_∞) is the odd independence ratio. (2) χₛₒ(Gd) = 3 for all d ≥ 1, where Gd is the infinite d-dimensional grid. As a consequence, od(Gd) ≥ 1/3. (3) The r-King graph G on n² vertices has αod(G) = n/(2r+1) ². Moreover, χₛₒ(G) = (2r + 1)² if n ≥ 2r + 1, and χₛₒ(G) = n² if n ≤ 2r. Many open problems are given for future research.