##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Sergey Kitaev

#### Reykjavik University

## Graphs represented by words

##### Abstract:

Given a word over some alphabet, we can form a graph with the letters of the alphabet as vertices, and with two vertices adjacent if those letters occur alternatingly in the word. A motivation for studying the class of graphs represented by words (in the described manner) comes from algebra, but another application is in robot scheduling.\\ \noindent When considering a class of graphs, several immediate questions pop up:\\ \noindent - Which graphs belong (and which ones do not) to the class,\\ - How large do the words need to be to represent all such graphs, and\\ - Can we come up with alternative representations that in particular make it easier to answer structural and algorithmic questions about these graphs?\\ I will discuss recent answers to these questions. This is joint work with Magnus M. Halldorsson (Reykjavik University) and Artem Pyatkin (Sobolev Institute of Mathematics).

### March 17, 2009

### 4:00 PM

### AP&M 7321

****************************