Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

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

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.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

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