Word-Representable Graphs I


Sergey Kitaev, University of Strathclyde


2017.04.21 09:30-10:30


Large Conference Room, Math Building


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?
The lectures will be dedicated to a comprehensive introduction to the theory of word-representable graphs, the main subject of the book “Words and graphs” recently published by Springer.
Lecture 1. Word-representable graphs. The basics.
Lecture 2. Semi-transitive orientations as the main tool in the theory of word-representable graphs discovered so far.