**Speaker**: Sergey Kitaev, University of Strathclyde

**Date**: Fri, Apr 21, 2017

**Time**: 09:30 - 11:30

**Venue**: Large Meeting Room

**Title**: Word-representable graphs

**Abstract**:

Suppose that $w$ is a word and $x$ and $y$ are two distinct letters in $w$. We say that $x$ and $y$ alternate in $w$ if after deleting in $w$ all letters but the copies of $x$ and $y$ we either obtain a word $xyxy...$ (of even or odd length) or a word $yxyx...$ (of even or odd length). A graph $G=(V, E)$ is word-representable if there exists a word $w$ over the alphabet $V$ such that distinct letters $x$ and $y$ alternate in $w$ if and only if $(x, y)$ is an edge in $E$. For example, the $4$-cycle labeled by 1, 2, 3 and 4 in clockwise direction, can be represented by the word 13243142.

Word-representable graphs generalize several classical classes of graphs, e.g. $3$-colorable, comparability, subcubic and circle graphs. Some basic questions to ask about these graphs are:

Which graphs are word-representable?

How many graphs on $n$ vertices are word-representable?

What is the minimum length of a word that represents a given graph?

We aim to give a comprehensive introduction to the theory of word-representable graphs, the main subject of the book “Words and Graphs” recently published by Springer. The lecture will consist of two parts:

Part 1. Word-representable graphs. The basics.

Part 2. Semi-transitive orientations as the main tool in the theory of word-representable graphs discovered so far.

**Slides**:
View slides