Overlap Graphs

Attila Por

Abstract

Let A={1,2,...,a} be an alphabet of size a>1. Consider the graph G=G(a,k,t) with the vertex set V(G)={v=v_1,...,v_k | v_i \in A}, the set of all k-letter words over the alphabet A. There is an edge between vertices v\neq w iff the last t letters of v are the same as the first t letters of w or the first t letters of v are the same as the last t letters of w (that is they overlap at t letters).

We will investigate the chromatic number \chi(a,k,t)= \chi(G(a,k,t)) of overlap graphs.