Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs

Amihood Amir, Michael Itzhaki

The palindromic fingerprint of a string $S[1\dots n]$ is the set $$\begin{gathered} PF(S)=\{(i,j)|S[i\dots j]\text{ is a maximal } \\ \text{palindrome substring of }S\} \end{gathered}$$. In this work, w…