deBruijn-like sequences and the irregular chromatic number of paths and cycles

A deBruijn sequence of order  kk, or a kk-deBruijn sequence, over an alphabet AA is a sequence of length |A|k|A|k in which the last element is considered adjacent to the first and every possible kk-tuple from AA appears exactly once as a string of kk-consecutive elements in the sequence. We will say that a cyclic sequence is deBruijn-like   if for some kk, each of the consecutive kk-element substrings is distinct.A vertex coloring χ:V(G)→[k]χ:V(G)→[k] of a graph GG is said to be proper   if no pair of adjacent vertices in GG receive the same color. Let C(v;χ)C(v;χ) denote the multiset of colors assigned by a coloring χχ to the neighbors of vertex vv. A proper coloring χχ of GG is irregular   if χ(u)=χ(v)χ(u)=χ(v) implies that C(u;χ)≠C(v;χ)C(u;χ)≠C(v;χ). The minimum number of colors needed to irregularly color GG is called the irregular chromatic number   of GG. The notion of the irregular chromatic number pairs nicely with other parameters aimed at distinguishing the vertices of a graph. In this paper, we demonstrate a connection between the irregular chromatic number of cycles and the existence of certain deBruijn-like sequences. We then determine the exact irregular chromatic number of CnCn and PnPn for n≥3n≥3, thus verifying two conjectures given by Okamoto, Radcliffe and Zhang.