Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs

The palindromic fingerprint of a string S1 n is the set PF (S) = \ (i, j) ~|~ Si j is a maximal \\ 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 1 n 1 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 O ( (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ₖ, which is the shortest string whose fingerprint PF (Sₖ) cannot be reconstructed using less than k characters. The results additionally solve an open problem presented by I et al.