# Noon lecture

On 12.10.2006 at 12:20 in S5, there is the following noon lecture:

# Overlap Graphs

## 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.

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010