Chromatic numbers with open and nonzero local modular constraints

Abstract

In this paper, we explore chromatic numbers subject to various local modular constraints. For fixed $n$, we consider proper integer colorings of a graph $G$ for which the closed and open neighborhood sums have nonzero remainders modulo $n$ and provide bounds for the associated chromatic numbers $\ddot{I}{‡}_n(G)$ and $\ddot{I}{‡}_{(n)}(G)$, respectively. In addition, we provide bounds for $\ddot{I}{‡}_{(n,k)}(G)$, the minimal order of a proper integer coloring of $G$ with open neighborhood sums congruent to $k\mathrm{mod}n$ (when such a coloring exists) as well as precise values for certain families of graphs.

24 pages, 2 figures