The column-interference graph and collision-free coloring for a sparse Jacobian

Let $m,n\ge 1$, $U\subseteq {\mathbb{R}}^n$ be open, $F:U\to {\mathbb{R}}^m$ be differentiable at $x\in U$, and $J:=JF(x)$ be its Jacobian as defined in The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case. A structural row pattern is a list of sets $S_i\subseteq \{0,\dots ,n-1\}$, one for each row $0\le i<m$, such that $J_{ij}=0$ whenever $j\mathrm{\notin }{S}_i$. It is a safe pattern only when every actual nonzero lies in the declared support.

The column-interference graph has vertices $0,\dots ,n-1$ and an edge between distinct columns $j,k$ exactly when some row support $S_i$ contains both. A proper coloring is a map $\chi :\{0,\dots ,n-1\}\to C$ to a set of color labels such that adjacent columns have different labels. For a color $c\in C$, its seed vector $s^c\in {\mathbb{R}}^n$ has coordinate $s_j^c=1$ when $\chi (j)=c$ and $0$ otherwise. The compressed product is $J{s}^c$.