Date: Fri, Apr 21, 2017
Time: 09:30 - 11:30
Venue: Large Meeting Room
Title: Word-representable graphs
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