  Fault-tolerant connectivity labelings are schemes that, given an $n$-vertex
graph $G=(V,E)$ and $f\geq 1$, produce succinct yet informative labels for the
elements of the graph. Given only the labels of two vertices $u,v$ and of the
elements in a faulty-set $F$ with $|F|\leq f$, one can determine if $u,v$ are
connected in $G-F$, the surviving graph after removing $F$. For the edge or
vertex faults models, i.e., $F\subseteq E$ or $F\subseteq V$, a sequence of
recent work established schemes with $poly(f,\log n)$-bit labels. This paper
considers the color faults model, recently introduced in the context of
spanners [Petruschka, Sapir and Tzalik, ITCS'24], which accounts for known
correlations between failures. Here, the edges (or vertices) of the input $G$
are arbitrarily colored, and the faulty elements in $F$ are colors; a failing
color causes all edges (vertices) of that color to crash.
  Our main contribution is settling the label length complexity for
connectivity under one color fault ($f=1$). The existing implicit solution, by
applying the state-of-the-art scheme for edge faults of [Dory and Parter,
PODC'21], might yield labels of $\Omega(n)$ bits. We provide a deterministic
scheme with labels of $\tilde{O}(\sqrt{n})$ bits in the worst case, and a
matching lower bound. Moreover, our scheme is universally optimal: even schemes
tailored to handle only colorings of one specific graph topology cannot produce
asymptotically smaller labels. We extend our labeling approach to yield a
routing scheme avoiding a single forbidden color. We also consider the
centralized setting, and show an $\tilde{O}(n)$-space oracle, answering
connectivity queries under one color fault in $\tilde{O}(1)$ time. Turning to
$f\geq 2$ color faults, we give a randomized labeling scheme with
$\tilde{O}(n^{1-1/2^f})$-bit labels, along with a lower bound of
$\Omega(n^{1-1/(f+1)})$ bits.
