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.
| Identifer | oai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-18096 |
| Date | 01 May 2010 |
| Creators | Knisley, Debra, Nigussie, Yared, Pór, Attila |
| Publisher | Digital Commons @ East Tennessee State University |
| Source Sets | East Tennessee State University |
| Detected Language | English |
| Type | text |
| Source | ETSU Faculty Works |
Page generated in 0.0023 seconds