SEMINARS
Word-representable graphs II

2017-04-21　10:30 — 11:30

Large Conference Room

Sergey Kitaev

University of Strathclyde

Jun Ma

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.