On a conjecture of compatibility of multi-states characters

Perfect phylogeny consisting of determining the compatibility of a set of characters is known to be NP-complete. We propose in this article a conjecture on the necessary and sufficient conditions of compatibility: Given a set $\mathcal{C}$ of $r$-states full characters, there exists a function $f(r)$ such that $\mathcal{C}$ is compatible iff every set of $f(r)$ characters of $\mathcal{C}$ is compatible. Some previous work showed that $f(2)=2$, $f(3)=3$ and $f(r)\ge r-1$. Gusfield et al. 09 conjectured that $f(r)=r$ for any $r \ge 2$\mathrm{.}Inthispaper,wepresentanexampleshowingthat$f(4) \ge 5$ and then a closure operation for chordal sandwich graphs. The later problem is a common approach of perfect phylogeny. This operation can be the first step to simplify the problem before solving some particular cases $f(4),f(5),\mathrm{.}\mathrm{.}\mathrm{.}$, and determining the function $f(r)$.