| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4649613 | Discrete Mathematics | 2009 | 7 Pages |
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.
