Summary: In [PS] a new family of subalgebras of the extended Z2-vertex colored algebras, called Klein-4 diagram algebras, are studied. These algebras are the centralizer algebras of Gn := (Z2 $\times Z2$) Sn when it acts on V $\otimes k$, where V is the signed permutation module for Gn. In this paper we give the Robinson-Schensted correspondence for Gn on 4-partitions of n, which gives a bijective proof of the identity [ (f $[\lambda ]$)2 = 4nn!, where f $[\lambda ]$ is the degree of the corresponding representation $\lambda $] n indexed by $[\lambda ]$ for Gn. We give proof of the identity 2knk = [ f $[\lambda ]$m$[\lambda ]$ where $\lambda ]\in \Gamma G$ k n,k the sum is over 4-partitions which index the irreducible Gn-modules appearing in the decomposition of $[\lambda ]$ V $\otimes k$ and m is the multiplicity of the irreducible G k n-module indexed by $[\lambda ]$. Also, we develop an R-S correspondence for the Klein-4 diagram algebras by giving a bijection between the diagrams in the basis and pairs of vacillating tableau of same shape.