Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs
<|reference_start|>Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs: The palindromic fingerprint of a string $S[1\ldots n]$ is the set $PF(S) = \{(i,j)~|~ S[i\ldots j] \textit{ is a maximal }\\ \textit{palindrome substring of } S\}$. In this work, we consider the problem of string reconstruction from a palindromic fingerprint. That is, given an input set of pairs $PF \subseteq [1\ldots n] \times [1\ldots n]$ for an integer $n$, we wish to determine if $PF$ is a valid palindromic fingerprint for a string $S$, and if it is, output a string $S$ such that $PF= PF(S)$. I et al. [SPIRE2010] showed a linear reconstruction algorithm from a palindromic fingerprint that outputs the lexicographically smallest string over a minimum alphabet. They also presented an upper bound of $\mathcal{O}(\log(n))$ for the maximal number of characters in the minimal alphabet.   In this paper, we show tight combinatorial bounds for the palindromic fingerprint reconstruction problem. We present the string $S_k$, which is the shortest string whose fingerprint $PF(S_k)$ cannot be reconstructed using less than $k$ characters. The results additionally solve an open problem presented by I et al.<|reference_end|>
@article{amir2024explicit,
    title={Explicit Combinatoric Structures of Palindromes and Chromatic Number of
  Restriction Graphs},
    author={Amihood Amir and Michael Itzhaki},
    journal={arXiv preprint arXiv:2406.04507},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.04507},
    primaryClass={cs.DS}
}