Degree Name
MS (Master of Science)
Program
Mathematical Sciences
Date of Award
12-2007
Committee Chair or Co-Chairs
Yared Nigussie
Committee Members
Robert B. Gardner, Teresa W. Haynes
Abstract
A graph G(a, k, t) is called an alphabet overlap graph where a, k, and t are positive integers such that 0 ≤ t < k and the vertex set V of G is defined as, V = {v : v = (v1v2...vk); vi ∊ {1, 2, ..., a}, (1 ≤ i ≤ k)}. That is, each vertex, v, is a word of length k over an alphabet of size a. There exists an edge between two vertices u, v if and only if the last t letters in u equal the first t letters in v or the first t letters in u equal the last t letters in v. We determine the chromatic number of G(a, k, t) for all k ≥ 3, t = k − 2, and a = 2; except when k = 7, 8, 9, and 11.
Document Type
Thesis - unrestricted
Recommended Citation
Farley, Jerry Brent, "Chromatic Number of the Alphabet Overlap Graph, G(2, k , k-2)." (2007). Electronic Theses and Dissertations. Paper 2130. https://dc.etsu.edu/etd/2130
Copyright
Copyright by the authors.