2025/10/02 by Caro, Yair, Petruševski, Mirko, Škrekovski, Riste +1
#05C09 #05C15 #05C63 #05C69 #05C76 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2510.01897
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 χso(G). A simple relation involving these two parameters and the order |G| of G is αod(G)⋅χso(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 ≤ \varrhood(P_∞ \Box P_∞) ≤ 0.384615..., where \varrhood(P_∞ \Box P_∞) is the odd independence ratio. (2) χso(Gd) = 3 for all d ≥ 1, where Gd is the infinite d-dimensional grid. As a consequence, \varrhood(Gd) ≥ 1/3. (3) The r-King graph G on n2 vertices has αod(G) = \lceil n/(2r+1) \rceil2. Moreover, χso(G) = (2r + 1)2 if n ≥ 2r + 1, and χso(G) = n2 if n ≤ 2r. Many open problems are given for future research.