On the Chromatic Number of the α-Overlap Graphs
Document Type
Article
Publication Date
5-1-2010
Description
The generalized deBruijn graph dB(a, k) is the directed graph with a k vertices and edges between vertices x = a1, a 2, ... ak and y = b1, b2, ... b k precisely when a2, ... ak = b1, b2, ... bk-1. The deBruijn graphs can be further generalized by introducing an overlap variable t ≤ k - 1 where the number of consecutive digits by which the vertex labels (sequences) overlap is t. The α-overlap graph is the underlying simple graph of the generalized deBruijn digraph with vertex label overlap 0 < t ≤ k - 1.We denote the α-overlap graph by Gα = G(a, k, t) and the parameters a, k and t are positive integers such that a ≥ 2 and k > t > 0. Thus dB(a, k) = G(a, k, k - 1). In this paper, we show that every a-overlap graph is 3-colorable for any a if k is sufficiently large. We also determine bounds on the chromatic number of the α-overlap graphs if a is much larger than k.
Citation Information
Knisley, Debra; Nigussie, Yared; and Pór, Attila. 2010. On the Chromatic Number of the α-Overlap Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing. Vol.73 3-13. ISSN: 0835-3026