#### 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* = (*v*_{1}*v*_{2}...*v _{k}*);

*v*∊ {1, 2, ...,

_{i}*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.