The odd independence number of graphs, I: Foundations and classical classes

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 $\hat{I}{\pm }_{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 $\ddot{I}{‡}_{so}(G)$. A simple relation involving these two parameters and the order $|G|$ of $G$ is $\hat{I}{\pm }_{od}(G)\cdot \ddot{I}{‡}_{so}(G)\ge |G|$, parallel to the same on chromatic number and independence number. We develop several basic inequalities concerning $\hat{I}{\pm }_{od}(G)$, and use already existing results on strong odd coloring, to derive lower bounds for odd independence in many families of graphs. We prove that $\hat{I}{\pm }_{od}(G)=\hat{I}\pm (G^2)$ holds for all claw-free graphs $G$, and apply this result to prove that determining $\hat{I}{\pm }_{od}(G)$ is in general NP-hard (and also when restricted to line graphs). We also present many results, using various techniques, concerning the odd independence number of cycles, paths, Moore graphs, Kneser graphs, the complete subdivision $S(K_n)$ of $K_n$, the half graphs $H_{n,n}$, and $K_p\square K_q$. Further, we consider the odd independence number of the hypercube $Q_d$ and also of the complements of triangle-free graphs. Many open problems for future research are stated. Further related results can be found in part II of this work, arXiv: 2510.01897.

added NP-hardness proof and some references inserted; 33 pages