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 $ψ$ on $X$ such that $Hom(\varphi) = Hom(ψ)$, either $ψ= \varphi$ or $ψ= 1-\varphi$. By $\mathcal{R}$ we denote the collection of all colorings reconstructible from their homogeneous sets. Let $\varphi$ and $ψ$ be colorings on $X$, and set \[ D(\varphi, ψ) = \{ \{x,y\} \in [X]^2: \; ψ\{x,y\} \neq \varphi\{x,y\}\}. \] If $\varphi\not\in \mathcal{R}$, let \[ r(\varphi) = \min\{|D(\varphi, ψ)|: \; Hom(\varphi) = Hom(ψ), \, ψ\neq \varphi, \, ψ\neq 1-\varphi\}. \] A coloring $ψ$ such that $Hom(\varphi)=Hom(ψ)$, $\varphi\neq ψ$ and $1-\varphi\neq ψ$ is called a {\em non trivial reconstruction} of $\varphi$. If, in addition, $r(\varphi) =|D(\varphi, ψ)|$, we call $ψ$ 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$.