  A coloring on a finite or countable set $X$ is a function $\varphi: [X]^{2}
\to \{0,1\}$, where $[X]^{2}$ is the collection of unordered pairs of $X$. The
collection of homogeneous sets for $\varphi$, denoted by $Hom(\varphi)$,
consist of all $H \subseteq X$ such that $\varphi$ is constant on $[H]^2$;
clearly, $Hom(\varphi) = Hom(1-\varphi)$. A coloring $\varphi$ is
\textit{reconstructible} up to complementation from its homogeneous sets if,
for any coloring $\psi$ on $X$ such that $Hom(\varphi) = Hom(\psi)$, either
$\psi = \varphi$ or $\psi = 1-\varphi$. By $\mathcal{R}$ we denote the
collection of all colorings reconstructible from their homogeneous sets. Let
$\varphi$ and $\psi$ be colorings on $X$, and set \[ D(\varphi, \psi) = \{
\{x,y\} \in [X]^2: \; \psi\{x,y\} \neq \varphi\{x,y\}\}. \] If $\varphi\not\in
\mathcal{R}$, let \[ r(\varphi) = \min\{|D(\varphi, \psi)|: \; Hom(\varphi) =
Hom(\psi), \, \psi \neq \varphi, \, \psi \neq 1-\varphi\}. \] A coloring $\psi$
such that $Hom(\varphi)=Hom(\psi)$, $\varphi\neq \psi$ and $1-\varphi\neq \psi$
is called a {\em non trivial reconstruction} of $\varphi$. If, in addition,
$r(\varphi) =|D(\varphi, \psi)|$, we call $\psi$ a {\em minimal reconstruction}
of $\varphi$. The purpose of this article is to study the minimal
reconstructions of a coloring. We show that, for large enough $X$, $r(\varphi)$
can only takes the values $1$ or $4$.
