Odd Independence in Grid Products, Chessboard Graphs, and Pentagonal Laves Tilings
Francisco González · Zenodo (CERN European Organization for Nuclear Research) · 2026
We study Problems 27–34 posed by Caro, Petruševski, Škrekovski and Tuza concerning odd independence and strong odd colorings in Cartesian grid products, pentagonal tilings, and chessboard graphs. For finite Cartesian products of paths and cycles, both parameters are characterized by finite transfer systems. For the square lattice, we determine the odd-independence density as 3/8 and answer the associated cross question. In higher-dimensional grids, we prove bounds implying that the odd-independence density tends to 1/2, disproving the conjectured limit 1/3. We determine the odd-independence density and strong odd chromatic number of the prismatic, Cairo, and Floret pentagonal Laves graphs. We also obtain closed formulas for rectangular Bishop graphs, determine the infinite Knight-graph density as 7/16, establish asymptotic results and finite transfer systems for Knight boards, and determine the strong odd chromatic number of the infinite Knight graph. Finally, we prove that every finite rectangular Queen graph, as well as the infinite Queen graph, has odd independence number one.