Minimal reconstructions of a coloring

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